The cause of the problem yesterday is found!
http://twitter.com/DNSMadeEasyDNS Made Easy, one of the largest, most reliable DNS services, and the DNS service we use is under a major DDoS from China (estimated at 30Gb/s). Though they seem to have gotten things completely under control by now.
This further explains why my monitoring service, my own browser, and other users didn't lose connectivity.
The monitoring service likely cached the DNS result, and since it knew the IP address, didn't need to look it up every time. Browsers tend to do this as well, to speed up the requests (which is why you might notice that the first time you open a browser in a day, it takes just a tiny bit longer to get to a page on the first load, and much faster thereafter - it's not checking the DNS anymore). Anyone who kept their browser open had a chance to not need to look up the DNS info again.
Fascinating.
If you want to read some of the technical discussion going on at Hacker News (a popular technical new aggregator, here's the link to the current discussion:
http://news.ycombinator.com/item?id=1583860 )