Concerning titles, In my state, the owner of record can get a new title for a couple of bucks. Storing all those titles and keeping up to date on where they are would be a lot more expensive. When I told a cop friend of mine I had misplaced my title, and kept putting off getting a new one, he told me not to bother, no one ever has them. If I got it now, eventually I would either lose that one, or find the old one, so it would be better to wait until I actually needed one. (like moving to another state, or selling the Car.)
I am sure Avis, Hertz, etc have all their cars titled in states that keep electronic records.