In the typical rental model the cars are either owned by a holding company or by a franchisee. In the typical DMV model there isn't a lot of other information other than "reported stolen." It may have been reported to an entirely different agency Local Police, State Police, Highway Patrol that whatever agency happens to effect the traffic stop.
You're expecting a traffic cop to perform a pretty thorough investigation, using just a cellphone and mobile PC, on the side of the road, without adequate facilities to properly identify the party on the other end of the telephone or even properly review the details of the initial report.
If it was your car that was stolen, I'm not sure you'd want someone trying to "Kojak" their way through the case. I wouldn't. Likewise, if I was pulled over in a rental and told it was stolen, I'd accept that the few hours of inconvenience I would face over it would easily be remedied and I would never rent from them again.
The police are functionaries with qualified immunity and no actual duty to protect or serve you. This is established law in the US. You want these people doing the most minimal, simple, procedural thing they can do in any given situation and you want to get yourself into an actual court as quickly as you can.
What do you mean? Rental car companies don’t have 24-hour, toll-free numbers, published on their websites? Police don’t have telephones?