DNS with Route 53

While Amazon gives you a free auto-generated domain name, I'm sure you would probably prefer your own.  Most cheap registrars don't allow you to generate real DNS records, they usually only allow you to enter the hostnames of other DNS servers (SOA records).  While you could go through the hassle of setting up a BIND server to handle those DNS queries, Amazon already has a nice fault-tolerant distributed DNS service called Route 53.  Unfortunately Amazon is not an ICAAN approved registrar so you won't be able to register a domain through them but it does have a powerful API and integrates nicely with SES.  It has a nominal fee of $0.50 per domain plus another $0.50 for every 1 million queries per month.

To use it, open the Route 53 tab and create a new hosted zone with the name of a domain you have registered at your favorite super cheap domain registrar.  After creation it will show 4 host names under the delegation set header.  You will need to enter those host names into your registrar as DNS servers.  In order for your domain to function correctly you will need at least one A record under your hosted zone.  Click 'Create Record Set' and make an A record with the default name and the IP address of your server in the value box.  I like to make a wildcard entry as well so I can make use of subdomains.  To do that, just create another A record and use * as the name and the IP address of your server as the value again.  It may take a few hours to propagate through the net but you should be all set.

Now all that's left is sending and receiving e-mail.