Can you make a recommendation? I want something in the middle of a cheap hosting like Dreamhost and Google/Yahoo/Rackspace.
It was difficult to find it. Dreamhost was great because I can create a lot of e-mail accounts for my company but in the last year there were a lot of outage that complicated my business. On the other spectrum Google/Yahoo/Rackspace could be great but they are expensive when there is a linear relationship between e-mail accounts and price, and we create new e-mail accounts all the time not only for employees but for testing specific pieces of software.
Honestly, I use Google Apps for Domains myself, behind a domain I own (so I can leave down the road if I want.) I don't think folks moving off Gmail to leave Google want to do that but it's worked well for me. It's been long enough that I can't remember what I used before that for my email.