Late to the Discussions, but i am surprise no one has mentioned atmail -www.atmail.com

They have a cloud solution too.

Personally i think this is the best email services.