I do something similar, and run multiple haproxy instances (failover clustered in each datacenter even) in several data centers around the world. I also needed GeoIP based traffic segregation to these different data centers, so I went with Dyn.com's "Advanced Traffic Management" solution, which allows different regions of the world to be served up to their fastest location globally, but also handles the monitoring and fail over like you are looking for. Dyn (and i'm sure others) offer solutions for monitoring/failover as stand alone offerings, e.g., http://dyn.com/dns/dynect-managed-dns/active-failover/
If you are trying to do this on the cheap, and when you say you haproxy is "down" means not responding due to a datacenter outage, you could try serving up multiple A records from your DNS server for each request. This would essentially round robin the requests to your different servers, and let the clients try the others if the first fails.
I do recommend going with a hosted solution though, as it's worked out great for me. I think DnsMadeEasy also offers a similar product for Geographic distribution that includes monitoring as well (for cheaper thank Dyn's).
You could of course build out some solution your self, but you should consider the all up cost of doing this vs focusing on your core service your company is offering. All about the trade-offs... :)
Also, if your DNS queries are crushing 50M/week, unless you have a lot of one time visitors (which i actually do) that sounds like a lot. Make sure your TTL settings aren't too low. If they are, you may be expecting you'll have to pay a lot more for a hosted service than you require.