Well, using any of the online services requires you to agree to their TOS; therefore, if you violate their TOS, they have the right to ban you from their online service.
I think you might have a case if there are multiple people sharing ownership device, since then other people would be punished for one persons actions. On the other hand, it may also be possible that the other people using the device could sue the person breaching Nintendo's TOS, getting the device banned and therefore reducing the devices value.
Generally, contract law can be extremely complex and the precise wording of laws is important. That's why I am asking for someone to provide links to applicable laws that restrict Nintendo's right as a private business to refuse service to a specific person as a result of that person previously breaching Nintendo's TOS.
I'm not trying to antagonize you, but I am just generally curious about this question. Hell, I'm not even certain at this point that the OP didn't actually do anything illegal, because he did purchase stolen goods and was likely aware of that fact due to the way his game was delivered.