If buying with a bill of sale only,
You should really have the state police come to the car and run the vin number before any money changes hand.
Actually, you can call any law enforcement and they can verify over the phone. This is not an uncommon thing they do. No personal data is revealed. You simply ask if its reported stolen, because you're preparing to buy without a title.
I can do this in California with Highway Patrol, County Sheriff and city Police. In my experience, the motor vehicle department is unreliable for this check. If the VIN is not in the law enforcement computers, it hasn't been reported stolen.
With a bill of sale you can sue the seller if they sell you a stolen vehicle. Further, you can sue for damages when the numbers get bigger, like this 30K+.
I bought a vehicle bill-of-sale only that turned out to be stolen. I got my money back because the police wanted to know who sold it to me. I followed the police over to the sellers house so I could ID the guy at the door.
It was then I learned I could simply call the police to verify prior to a sale, but, you MUST have the VIN number, as license plates are not a reliable way to identify a vehicle. I've done this from a cell phone in a sellers driveway. Only one other time have I (nearly) purchased a stolen vehicle.
Also, in California, if the vehicle was NOT Non-Op'ed prior to the registration expiring, the NEW owner is on the hook for paying back due registration fees. So any vehicle not currently registered, it's worth a trip to the motor vehicle department to confirm fees to transfer title.