I'm thinking it mightn't be a terrible idea to run a cron script each night (or more often, if you've got cycles to spare) that generates a bunch of fake domains, checks them for nonexistence, and dumps them into a text file. Then you could use that as a dictionary. I'd say that would be too much overhead for an on-the-fly job, especially one designed to be hit a lot, but keeping that file filled and fresh wouldn't be hard.

LAI