They also state in their sales page: http://www.domaintools.com/sponsor/

That the aboutus.org links shown when looking at a particular domain are bought and paid for, with juicy metrics to boot.

Thanks for the coverage and good point John. If you check Google's backlinks to the vps landing page you'll see it is the real deal. Worth also pointing out the vps landing page has a PR of 6 same as the home page.

I just feel like Google should be aware of this issues because it sends the wrong message about an already controversial topic.

When I checked this morning it looks like the ad at
http://whois.domaintools.com/example.com
now has a redirect through "/go/", which has a robots.txt blocking /go/ .

(Added an update, thanks Matt!)

They better get busy writing their reconsideration request and document the change to redirecting through the /go/ folder. It seems like their impending PageRank penalty hasn't filtered through the datacenters yet, but it would be good to get ahead of it. They should get their PageRank back in a couple weeks if the reconsideration request is accepted. If it's not accepted the PageRank penalty will persist until they fix and document any other discretions and file another reconsideration request. They won't get any feedback so as to not tip off the die-hard spammers.

At least that's the process I've seen for many sites that aren't partners with Google and get caught selling links.

Matt
Sorry for causing any headaches but thanks for addressing as well as resolving this issue so quickly! I've updated my post...