Every game that had a LAN mode could generally be played either via a software VPN, or other methods. More often than not games (especially FPSes) would ship with dedicated server software. You still needed to buy the game, but then you could run the dedicated server on your favorite hosting platform and play.

I think it was the xbox-ification of shooters that changed everything. 2009 or so, if I had to guess. MW2 was the first game that I remember really pushed company owned servers hard. Coincidentally this was also used to sell overpriced, often useless, DLC. At least back then the DLC was maps though.

It might be my age but I find it easier to remember games that DID have dedicated servers, rather than those that don't.