The trouble with Carfax is that it's totally dependent on garages/financial institutions/government agencies to report and only some of them do, and some only do it intermittently. It's handy for detecting things like odometer rollbacks and "cleaned" salvage titles, but it isn't a definitive vehicle history. I wouldn't discount the car just because of that seemingly unresolved item, but I would definitely give it a little more scrutiny.
The procedures for liens and vehicle titles are wildly different from state to state, so this is really a question with 51 answers. Just because the dealer has a clear title in hand does not necessarily mean there's no lien-- think of things like mechanic's liens where obviously the lienholder usually can't get their hands on the actual title. If I were you, I'd call whatever agency you go to to transfer the title and ask them how to check for liens. If you're in a state where the dealer usually handles it, actually call the agency's office. They should be able to just tell you over the phone if the car has a lien in their database, although this might not discount an out-of-state lien.
Like I said above, I wouldn't be too worried, but be sure to do your due diligence since you know the lien existed once. And if the dealer is being evasive, just walk away.
Last edited by GreasyJack; 01-13-2011 at 07:25 PM.