I had a domain like this that I acquired years ago. Someone sitting on it for years had used it for junk ads for pr0n. Google and Yahoo wouldn't touch it, even after it had obviously changed owners and the content was 100% legit for more than 2 years. All the searches for it being on blacklists, etc., came up with nothing...running through code and SEO checkers gave it flying colors. No obvious reasons for it not being shown. It only appeared on Google after they did an update. I still have no idea what the cause was, but can only assume it was because it was blacklisted way back.
The point. If you find it blacklisted somewhere or anything obvious like typing domain.com not showing up in the engines, then you know. But if not (and this domain would show up typing domain.com but NOTHING else), it does not necessarily mean that it is clean.
$0.02