If you get a domain name that someone else had, but didn't renew, does Google know it's starting over? What if it had been penalized before? Do the search engines look at the WhoIs data and know that it's really a brand new site? I imagine that if there are any links out there on the internet and you put up a site, they'll pass juice, right?
They know when it's changed hands. They are afterall domain registrars themselves. If it were penalized before then once you get your site up and are sure that it is in compliance w/ Google's webmaster guidelines, I would submit a request for reconsideration.
Google can track across multiple IP and Domains owners, so they are smart enought to figure out if a domain changes owner. But if the inbound links still keep coming in and the content matches then they will count.