you should always keep in mind, that if you delete the contacts from your phone book, they'll be deleted from the server, too..
at least in skype and icq this is the case, can't tell surely for aim, but i don't think it differs per service...