Someone has to eat the loss: the original owner or the last purchaser. The question is, between the two who is the "least cost avoider"? That is, the one who we can most easily incentivize in order to arrive at the best overall outcome.
In short, if the last purchaser got to keep the car, that means he would be less risk averse to buying from car dealers with risky reputations, effectively increasing the market for stolen cars. And this increase in the market would result in more stolen cars overall.
The existing default rule is, of course, based on a judgment that we won't be worse off in a world where people can fraudulently claim that their car is stolen and then get it back while also capturing the sale profit. Considering that most people are law abiding and have very good reason already to protect their car from theft regardless of which default rule we choose, it's not a bad rule on its face.
> in an ideal world, I think there should be some sort of safe harbor protection for people who make a reasonable effort in good faith to check that a transaction is bona fide.
It sounds like you may have a legal education given the language you're using. IIRC this is how the rule for real estate works in the presence of land registration systems. We flip the default rule to incentivize recordation. If two fraudulent sales are made by a seller back-to-back before title is recorded, it's the last purchaser who gets the property. This incentivizes each purchaser to record his purchase as quickly as possible, and to do so in a manner that closes the window for a fraudulent sale, such as by keeping payment in escrow until recordation is successful. (See, e.g., https://en.wikipedia.org/wiki/Bona_fide_purchaser)