Als je met je webbrowser inlogt op je hotmail/outlookmail, kan je van daaruit doorklikken naar Messenger, waar onder Personen->Beheren een optie tot Uitnodigen bij Messenger staat.
Ik heb dat zelf nog niet hoeven gebruiken, maar het is een poging waard.
Edit:
een andere manier om buiten Skype om nieuwe msn-contacten toe te voegen is wellicht via je oude chat-programma (Pidgin en dergelijke), met een beetje geluk zie je ze dan in Skype verschijnen.