I'm using Mandrill for sending mail from my Heroku-based rails app, and my domain and dns is hosted with Fasthosts. To ensure deliverability and high reputation Mandrill recommend you add DKIM and SPF records to your domain, and they provide instructions on how to do this.
Unfortunately I had trouble getting this right with Fasthosts, until I found this in a Mandrill troubleshooting guide:
If your domain has an SPF type record, it's best to add a matching TXT record for wider compatibility.
This solved my problems. Here's how it looks in my Fasthosts control panel: