I don't think there is a way to see if it's 'banned' per se. It may be deindexed based on content, but that's not permanent and throwing something new and unique out there will likely get it back in no time.
When I'm looking at a domain's history, one of the first things I do is I check it's yahoo link directory:
http://siteexplorer.search.yahoo.com...h?p=domain.com
and just do a little footprinting on it. If it's been parket, then unregistered, good chance you won't have issues with a new whois/nameserver/ip/etc.
For easy footprinting of domains, download SEOQuake for FF/IE. It's a handy little toolbar that lets you see a shitton of info about a domain/page.