I remember XBConnect and GameSpy for playing Xbox Halo 1 over the internet. I think a couple were invented for every big game or console before 2010 or so.

Tailscale doesn't really address connecting to strangers, though.