We don't have our own server either. There is a hosting company called
Webville Networks that the company uses. This company even put out a
publication on how to setup the email on the iPhone.
We looked and considered a couple of them and in fact even signed up with one, but the cost was a pretty good bit considering the number of accounts we'd need. Then I did the nonprofit partnership agreement with Google and FREE is hard to beat.
In my testing I don't find these other providers like Mailstreet, GoDaddy (the two main ones I tested) etc to be any better than Goggle for us. But then again for me operating a nonprofit I was looking for a low cost or even no cost provider and that is what Google does for us.
Glad your work provider works well for you!