Updated on February 27th 2012, see bottom of this post.
I finally decided to quit Google Apps as my email provider. After exploring and analyzing alternatives, I settled with FastMail.
My mailbox is very important to me and I’m sure you feel the same about yours. I wouldn’t ask anyone I don’t trust to take care of my personal items. Same goes for my emails. It was a logical step to move them out of Google’s grasp. Thus began the search for the perfect email hosting service supporting custom domains.
THE ALTERNATIVES
The popular alternatives were the following :
I expect a very high uptime for my mailbox. One running on a shared web hosting plan, VPS or dedicated server was not an option. I don’t want to spend time managing the server side of my mailbox. They all fail once in a while, whatever the company and/or setup. It’s also more expensive.
Feel free to let me know about any services I missed. I’d love to expand the list because I found the options to be quite limited.
It seems Media Temple is cooking a new email service. Check the Media Temple Product Roadmap for details.
FASTMAIL.FM
I ended signing-up for FastMail after reading Marco Arment’s recommendation of this service.
FastMail is now owned by Opera. They are experimented, apparently stable — still early to judge but their pingdom is available to the public — easy to setup, well documented, etc.

The interface is oldschool, don’t expect anything like Gmail. Although, I found it to be working just fine for handling configuration, aliases, domains, etc. I always use Apple Mail under OSX or iOS anyway.
I had to contact the support team once after signing-up and received an answer in about 24 hours.
The Personal Enhanced plan starts at US$39.95 per year. Less than $3.50 per month. This allows unlimited custom domains.

Custom (Virtual) Domains
It’s very easy to setup. You can be up-and-running within 5 minutes if you force your domain’s DNS settings (MX in this case) at your registrar to refresh at this rate. Full propagation will of course take 24-48 hours as usual. This means some emails might end up on Google Apps’ side while others on Fastmail’s side during that time.
It is worth noting that custom domains at FastMail are handled as virtual domains. This means that you will only have one mailbox — username@fastmail.fm — and all your configured aliases and domains will direct to this mailbox.
Unlike Google Apps, you cannot create mailboxes for other users. If you need this kind of feature, you must go with the Family or Business plans.
This can be an issue for some people, depending on your email client. Let me try to summarize why :
When you wish to send emails from one of your custom domain — username@mydomain.com — you will need to configure your email client to use this address in the From field of your emails.
If you have multiple domains and you want to be able to send from each of them within Apple Mail for example, you can add multiple entries to the From field of your account configuration by putting a comma in-between such at username@mydomain1.com, username@mydomain2.com, username@mydomain3.com, and so on.
After, you simply select the email to send from within the new message window.
Unfortunately, you cannot define multiple names (personnalities) in Apple Mail. Whatever domain you choose to send the email from, the same name specified in the account settings will appear as the sender.
Some email clients — such as Postbox — support multiple personnalities.
To setup multiple domains to use in iPhone’s Mail, you can enter the domains into the Address field inside your IMAP Account preferences. You must separate each domain by a comma (see the example for Mail.app on OSX above). The problem is that the comma character doesn’t appear on the keyboard for this input. You will have to manually Copy & Paste it from another field to this one.
Overall — even though it sounds complicated — the whole setup is fast and easy. Just take the time to read the Help provided and you’ll be fine.
Migration

FastMail offers a migration tool that will fetch any IMAP mailbox and transfer emails from your current/previous provider to your new account. Migrating from Google Apps to FastMail was done in about an hour for approximately 2GB of emails. It works in the background and notify you by email once it’s ready.
CONCLUSION
Until now, FastMail is proving to be the right choice. I also feel much better knowing my mailbox is free from ads and into trustworthy hands.
You can always create a free account on FastMail and try things out yourself to see if it fits you. Unfortunately, you won’t be able to see the domains management feature until you upgrade to the Personal Enhanced plan. If you do so, feel free to use my referral code so I get a tiny kickback.
UPDATE (February 27th 2012)
It’s been many months since the switch. According to the traffic generated by this post, it seems a lot of people are considering FastMail as an alternative to Google Apps. I thought I’d post a quick update.
I’ve been extremely satisfied with FastMail in the past months. I have yet to see any downtime.
They are also testing a new webmail UI (in beta) to improve the look of the aging one. Don’t expect anything near Gmail’s interface though.
I do have to mention the only downside : I’m receiving a bit more spam in my inbox. Maybe 2 or 3 a week (but sometimes 0). It used to be none when using Google Apps.
So for all of you investigating on FastMail, I am most definitely recommending it.