...So it seems that every time I've rented a car internationally in the last 10 years I've been driving without insurance...
Not necessarily. I know for a fact that in Germany, (unlimited?) liability insurance for car rentals is mandated by law, and all rates for car rentals quoted there must include it.
I think (but don't know) that may be the case in other EU countries.