Comment by paranoidrobot

Have a cache of domains you know about with registration date.

When getting a query for a domain you have not heard about, query whois for it. Store it's registration date in the cache.