Dynamic subdomain routing

I asked this question over at stackoverflow, but got very few views: https://stackoverflow.com/questions/2284917/route-web-requests-to-different-servers-based-on-subdomain

Perhaps it's more applicable to this crowd. Here it is again for convenience:

I have a platform where a user can create a new website using a subdomain. There will be thousands of these, eg abc.mydomain.com, def.mydomain.com . Hopefully if we are successful hundreds of thousands.

I need to be able to route these domains to a different IPs to point at a particular app server. I have this mapping in a database right now.

What are the best practices and recommended technologies here?

I see a couple options:

1. Have DNS setup with a wildcard CNAME entry so that all requests go to a single IP where perhaps two machines using heartbeat (for failover) know how to look up the IP in the database and then do an http redirect to the appropriate app server. This seems clunky and slow to me.
2. Run my own DNS server that can be programatically managed such that when a new site is created a DNS entry is added. We also move sites around to different app servers, so I would need to be able to update DNS entries in close to real time. Thoughts anyone?

Thanks.

Update2: I've setup external wildcard DNS pointing at an HAProxy web server whose job it is to route requests to backend servers. The mapping is stored in our internal PowerDNS server. Question now is how to get the HAProxy server (or another) to use the value of the internal DNS and not some config file or access list? –

Update: Based on some suggestions below, it seems like reverse-proxy server(s) is the way to go. As I'll be rebalancing the domain->server mapping, these need to work instantly and the TTL on a DNS solution could be a problem. Any recommendations on software to use considering this domain->IP data is stored in a DB, and I'll need this to be performant?

Given your requirement for real-time failover between servers I couldn't recommend a DNS-based solution - too many clients will simple not spot the changes.

Are all these servers going to be on one site? A resilient front-end "reverse proxy" with access to the customer -> sever mapping table would seem to be easiest.