9.05.701 - printing slow

We are on 9.05.701. We run a hosted solution with our servers at Backspace.
Our printing performance has ALWAYS been terrible, since we went live a year ago.
It can literally take 5 minutes from the time you click print until the printer responds.
Any ideas on how we can improve this performance? We've upgraded our internet and that hasn't really solved the problem.