> How did the older games actually accomplish this?
Using Counter-Strike as an example: no matchmaking system - relied upon community hosted servers offering a wide range of game modes (official and community created). More competitive matches (pick-up games) were often found via IRC.