There was a 'full-disclosure' thread on this recently:
http://www.derkeiler.com/Mailing-Lis...5-06/0169.html <--archive

I suppose they regularly download zone files (as published by Verisign
and others), and perform A record lookups on all listed domains.
Probably they try domains prefixed with "www" as well.