Aforementioned UT1 (all UT's though, really, to be true)
Aforementioned Morrowind
BG2's special vendor got added in the patch.
Heart of Winter for Icewind Dale
Multiplayer for Deus Ex (it sucked, but was free!)
DLC maps for Majesty and X-pack (you asked which I remembered)
The Sims got free stuff. Now even these are paid, if you don't include the dozens of x-packs
Dungeon Siege and expansion got bonus missions.
That's all I can think of right now around the 2000 timeline.
I'm still under the impression that the extra vendor for BG2 wasn't included in an official patch, but both of them had to be added via unofficial hacks (then from Baldurdash, now via weidu).
Heart of Winter was a paid expansion. Trials of the Luremaster wasn't, but I believe riots were breaking out over HoW's shortness, which is why it was done.
I don't think we've exactly blown my prediction of ~5 out of the water, here, certainly not in a scope that would say that in the good old days, dlc was free, certainly not in a scale that would be significant in any way.