A friend of mine believes he got stung on this issue. A particular domain of his has never been able to get into Google's index, and remains permanently PR-0. He suspects it was a banned domain.
I know of one web-based whois search that apparently offers this as a paid feature.
Be careful it may only be a history of who has looked at the domain using their page! not a history of the domain!
The easy way to check without signing up is to view the domain, click Ctrl + refresh and see if the Number of "Whois History:" records stored increments by 1 ;)
Their "Whois History" record now contains another record - Your IP address