I got pointed to this thread by reading an interesting post on Search Engine Roundtable. It talks about how Google (now being a Registrar as of January 2005) may be reading the nameserver and/or whois data.

I believe that Google have been doing this for sometime now - but by using the Google Toolbar to help locate new domains - although I'm sure many would disagree.

Potentially with the PageRank feature enabled, Google do have the facility to monitor every page you visit. I have domains that are private to me and never received any inbound links yet they are appearing in Google (one in particular has a very obscure name yielding just 4 results in total with mine being at the top).