To answer your edit: There are services that sell lists of newly registered domains. Not sure how they create these lists in the first place. They probably hook themselves into the DNS and keep track of changes.