Skype lets non-contacts IM you? Wonderful
That would be a bit of a PITA getting a new contact ... you would have to meet (game, chat room, forum, etc), exchange your info, then add them to your list. If one person gets it [info] wrong, neither can re-communicate (unless they find each other again).
There should be an option to disable non-contacts IMing you before you've approved them though. Kind of like how MSN works.