Linode. The only issue is my app creates subdomains on signup, and it takes about 5 minutes on linode to become active.
You can even do this for MX records with Linode, thanks to their excellent support staff adding the functionality to their DNS interface when I asked for it. :)