I thought I'd seen discussions on this before but a couple of site searches and checking discussions back to May didn't turn up anything obvious.
#1) Go to archive.org, and enter the domain name there and see if anything pops up. If nothing shows up this doesn't prove that the domain name is clean, since there could have been a site up at that domain before that blocked the archive.org bot. However, if there was a site at that domain and they didn't block the bot, you've just hit the motherlode. Not only have you found there was a site there before, but you can even view what the site was like to see if it seemed shady.
#2) Using multiple search engines (IMPORTANT: NOT just Google), enter the domain name you are interested in the search box. It seems to me unlikely that if a site was significant and dirty enough that Google decided to zap it that there wouldn't be any dangling inbound links to it still around. Again, this isn't probative as it is possible that no inbound links survive. However, it's worth the effort to do this.
