I think you are blaming Amazon for a problem that is inherent in DNS, or possibly your approach to handling your DNS based features.

Unless I've drunk too much AWS Koolaid, I'm fairly certain you can run wildcard DNS for just the MX records for your domain. That entry would look something like:

*.example.com. 3600 IN MX 10 mail server.example.com.

Your mail servers can take the DNS synthesized domain from there I think.

BTW, I agree serving naked domains is a bit of a PITA, (appengine problem too!) but you can solve that by assigning a few elastic IPs to a few web heads and use RR DNS for them, with some code to take them out if one fails. Zerigo, for one, supports doing something like this IIRC.

302 anyone using the naked domain to the www. I doubt it matters much load wise as it sounds as if your running subdomains for your app like we do at Loggly.