Don't know about NC, but here in Nebraska you can go to wherever the vehicle was registered last and get a duplicate title for $14.
When I was in high school, I had a pickup. It was actually titled to my father. When I joined the Marine Corps, it was parked on the farm and pretty much abandoned. A neighbor did some custom work for my father, and instead of cash payment, he asked if he could have the pickup. So my father gave it to him. The title was never transferred. The neighbor just parked the pickup and never got around to doing anything with it.
Fast forward some 30 years. A fellow wanted to buy the pickup from the neighbor. By then, my father had passed away, and who knows where the title was. At that point, there were still channels to go through to get the title on the vehicle. I remember my mother needed to sign an affidavit that my father had owned the pickup, etc. Can't remember the rest.
Best thing you can do is start with your local DMV and work upward.