Seconding this recommendation. Their email hosting also lets you set up multiple accounts per domain, and a huge number of email aliases for those accounts, so that you can easily create service-specific addresses or addresses that forward to multiple places.

If you want more storage than their default 1GB, I suggest running your own IMAP server and running getmail to download all your mail continuously, while still using their SMTP server for all incoming and outgoing mail to avoid having to worry about deliverability. getmail supports IMAP IDLE, so it can download new mail and add it to your IMAP server the moment it arrives.

(Or, if you don't want to do that, you can pay Gandi for more storage.)

I've used them and I recommend them, but the 1 GB included with their offering is not enough, and additional space is ridiculously expensive.