I am using FastMail since the beginning of this year and I couldn’t be more satisfied. Service is fast, reliable and I do not have to run the mail server myself. I will jot down Gandi DNS settings for further reference.
FastMail DNS configuration page (reference).
Equivalent Gandi DNS configuration (expert mode/BIND version 9).
* 10800 IN MX 10 in1-smtp.messagingengine.com. * 10800 IN MX 20 in2-smtp.messagingengine.com. @ 10800 IN MX 10 in1-smtp.messagingengine.com. @ 10800 IN MX 20 in2-smtp.messagingengine.com. _client._smtp 10800 IN SRV 1 1 1 sleeplessbeastie.eu. _imaps._tcp 10800 IN SRV 0 1 993 mail.messagingengine.com. _pop3s._tcp 10800 IN SRV 10 1 995 mail.messagingengine.com. _submission._tcp 10800 IN SRV 0 1 587 mail.messagingengine.com. _caldavs._tcp 10800 IN SRV 0 1 443 caldav.messagingengine.com. _carddavs._tcp 10800 IN SRV 0 1 443 carddav.messagingengine.com. @ 10800 IN TXT "v=spf1 include:spf.messagingengine.com ?all" mesmtp._domainkey 10800 IN TXT "v=DKIM1; k=rsa; p=MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC4YBuGB6cAlBK/rGwhGhaSupAUQffnUqU/TMUNTO+WyOV5QbVg0e+YrPfThZwnPEQv3HOOIDpmVbPwGZZqOSM3/j3p90KQW2VVMJky86BFGmRg8D8GFIuVMqFluQ6Bg5IFhQZDh1LrowpsuyCZdocc97+eKyWYvfzYiuHPKqhofQIDAQAB" _adsp._domainkey 10800 IN TXT "dkim=unknown"
This is the way I have configured it.