Question for the opening poster: you named Gandi.net yourself. Do you have any negative experience with them prompting you to search for an alternative? Or are you just interested in comparing different options?

I had this problem with them and I didn't understand the explanation:
http://www.emaildiscussions.com/showthread.php?t=73751

I continue with them in 1 of my domains, but now using it with Fastmail.
I hope that the support service answer faster now than this past months...
So, my new domain was created with Namesilo and working with Fastmail too.