I researched Virginia's process for a replacement title some time ago, but never had to follow it as circumstances changed for me. It seemed difficult and the customer svc reps on the phone weren't much help. Here is a link:
The last time if went and spoke with them years ago they told me I would have to search surrounding states and keep my search expanding until i found something. It’s also $50.00 a state. What a rip off still Not guaranteed to find it. When I typed the vin on google search there was a member on hear who owned what was left of it back in 2004. His user name was brokekycpl
The OP appears to be operating on the unstated premise that the car was previously titled in Virginia and the title was "lost". If that is indeed the case, what facts/evidence exists which supports that premise?
If the VA DMV records show an owner of record, reconstructing the chain of ownership from that starting point should be a logical process reconnecting all the links.
If, on the other hand, VA DMV records have no evidence of the car being titled in that state, it seems to me that the process should be that of an original application for title in VA. The lack of adequate proof of ownership coupled with the value of the car being above a minimum threshold would likely involve a title bond. It's done every day. There is a cottage industry that exists which addresses this failure to do ones due diligence before handing over money to the person claiming to be the lawful owner of the car.
The random hopscotch of surrounding states at $50 a pop has no basis in reality. How does a clerk in VA know what other states might "charge" for a records search in another jurisdiction?
If the VIN has been tampered with, that is a whole other level of complication and may result in a State issued VIN being assigned to that car.
A search of this forum's archives will turn up multiple threads cautioning against buying a car without a clear title/ownership history. To buy a car without a title can be an issue, especially if the VIN turns up on a stolen car list.
I am aware of several examples of a valuable car being impounded and returned to the rightful owner, or their insurance company decades later. Buying a car twice is generally not a sound financial strategy.