This site enables you to query its reverse dns lookup (IP to hostname) database. The use of this webinterface via non-automatic tools is free.
Pricing for the direct interface to the database engine.
Help by adding hostnames to the database.
Other free services:
search IP database for hostnames
search for other virtual hosts for hostname
One way is to scan your browsercache and submit the found hostnames through the form below.
To extract those hostnames use one of the following scripts:
cd ~/.kde/cache-localhost/http;perl <path to script>konqueror.pl
cd ~/.mozilla/firefox/default.cqf/;perl <path to script>firefox.pl
Both scripts create a file names hostname.txt in the current directory. Just copy&paste the content into the form below.
You can filter some hostnames if you think they should be private. The scripts don't communicate by themself.