Obligatory mention of the project that aims to provide a replacement service, at least for Wii games.
MK Wii works just fine with that replacement server. You'll have to create a new profile though, but for Mario Kart it's not much of a problem - just use cheat to get to unlock everything so you won't have to open every car and character again.
Nooo, I used to enjoy playing Tetris DS online (although I nearly always lost). Is there any replacement service for the DS?
I checked the site further and their seem to be notes on the DS Wi-Fi protocol too. There's a patch for Mario Kart DS too, so I presume they are working on it.