If they're msn contacts chances are they never really got deleted in the first place, practically impossible to delete contacts there. They will reappear when you least expect it.
If it's ICQ though then you have to start from scratch cause icq doesn't store them on a server.
