Check out this:
http://www.alltheweb.com/search?adva...xx.xxx.xxx.xxx
Replace the xxx.xxx.xxx.xxx with the IP of the server you want to check, and it will return all the pages in it's search engine that were on that IP last time it crawled.
I've tested it a bit, it's not bad... about 70% accurate I'd say - but the main problem is it will list multiple pages/urls from the same site...
... but hey, it's better than nothing, and I just thought I'd let you guys know about it - since whois.sc is charging now.