I use hostmonster.com and have for a few years and I am very happy. I switched to them when my last provider pretty much got non-responsive, had intermittent service and just plain stunk.
Hostmonster has 5.95 per month for nearly unlimited service. (BTW - any time they come out with a new promotion, I just call and they upgrade my service with no cost and without a hassle. It seems the new offer is unlimited storage, bandwidth, etc.)
I use both the secure email and non-secure email as needed (for OpenGoo) and they both work fine. I have probably 30+ email accounts on there but it will allow you pretty much unlimited accounts.
I am not currently hosting my OpenGoo on there yet but they do support PHP5 and MySQL so I may see how it runs on there in the next few days.