DKII on 22 April 2007
Most games still have random matchups without needing friend codes, you just can't talk to anyone. It's not like you are prevented from playing at all. Though Pokemon DS at least is an exception to this, I know MarioKart, Metriod Prime Hunters, and Star Fox allow random battles.