I know what you mean. I stoped adding every Tom, Dick and ...er..Sally for that reason. Now I make a list on my Signature to show who needs to add me to thier list. Its nice to get used to this now before the online multi-player games come out. Good Luck...
PS. Yes both users have to register each other in order to work, so let them know you want to be added to thier Wii too.
Wii ya later,