@Firebird8 The difference is, that if I am deleting contacts from my IM client or IM aggregator, I fully expect those contacts to be gone. When I am deleting contacts from my phone's phonebook, I do not think of IM clients.

@johnnyrockets911 No, they are not gone if you just signed in to Gtalk or Skype on N900. Actually they are in your phonebook, and it's super convenient. But if you delete Gmail, Skype or any other contact from your N900 "Contacts", they will be deleted from those services servers too.

@sharper Thank you very much. This is the first hope that I may actually have those contacts restored. Thank's again. I will definitely try that

@horus Thank's. I'll try that too.

Wow, this one's a one helpfull community. Waited a day from making the post on my blog and twittering. Didn't get a single helpfull reply. 20 mins here, and I have almost solved them. Wow