Yeah what kind of car maker would pioneer something like that?

You must be thinking of OnStar :-)

Tesla's implementation is materially different in that it's not optional and cannot be trivially disabled.

Early Onstar vehicles are trivial to disable and later ones can still be disabled by removing the radio transceiver. The vehicle operates normally without it, unlike a Tesla.

False. Tesla data sharing is opt in only and the car works fine when sharing is not enabled, the default.

Does the car work if the cellular connection is physically disabled?

Of course.

Yes, otherwise it would be unusable by anyone living in a city, given that underground parking (esp multi-level one) tends to have no reception at all. Not even mentioning driving through countryside stretches on road trips.

The only things that won't work with no cell connection while you are in the car are things like spotify app in the car (but you can still use spotify through the car bluetooth connected to your phone, if you preloaded the songs on your phone) or being able to see live stats of the car in your phone app.

I hope you're not thinking about Tesla? This long predates Tesla.

Sure. There are fleets of automated license plate readers, there are patents about tracking serial numbers broadcast by tire pressure sensors, etc. States sell their entire drivers license databases as well https://www.vice.com/en/article/43kxzq/dmvs-selling-data-pri...