E-Mail Hosting Suggestions?

We currently have our e-mail hosted through our web hosting company, “1and1”. We have been experiencing a lot of problems with very delayed and lost e-mail, both incoming and outgoing. They seem concerned with fixing the problem so we are looking into solutions.

Hosting our own e-mail is not an option right now, but it is something we are working towards in the future.

Does anyone have any suggestions on a rock solid e-mail and web hosting company? Our business relies heavily on working e-mail. I thought 1and1 was reliable, they are not.

Any suggestions from experience would be greatly appreciated!