Here's a design for a "joystick router" that sends joystick presses over the Internet. You'd need some kind of hardware interface from PC to console, but this system and software could be generalized to any console game system. It works with existing games and does not require any changes to the console. In fact, since the joystick goes through the PC first, you could use any PC-connectable joystick as a control method for the console game.
software init: Synchronize timestamps with remote machine
loop: record a local buttonpress to the buffer with "received timestamp"
log incoming buttonpress packets to buffer with "remote received timestamp"
if the time is right send both buttonpresses at the same time.
goto loop
I can already think of a number of situations where this design won't work - console switches aren't emulated, you can't start both machines at the same time, there is no way to ensure the machines are synchronized, latency will always delay buttonpresses so players have to learn to lead their actions, random number generation differs per-console, tradeoff between TCP (slower) and UDP (have to handle dropped packets) etc. But it may be useful for strategy games or slow-paced gaming.
I may build it if I get some free time. You could then set up that matchmaking service (I already have a working server browser design) to find available gamers.