Well I deleted the contact-cache after removing a contact (I guess) and today the contact appeared on my list again.
I will now delete the contact-cache first, then login on WLM, then delete the contact-cache again, then I will remove the contact, then I will delete the contact-cache again...
I will even delete the contact-cache on another computer which I hardly use anymore...
If the contact will come back, I could try another program, but I don't think that will cure the problem.
By the way. there were some maps in C:\Documents and Settings\<user name>\Local Settings\Application Data\Microsoft\Windows Live Contacts which were the result of a mistyped username when trying to logon. I deleted these maps too and they have come back too!
The contact appeared again...
I logged in on webmessenger.msn.com and all the deleted contacts were gone....
When I logged in again with Live Messenger they were there again.
So, it looks like on MSN's server the contacts are gone but somewhere on my computer they're still there and because of that they keep coming back.
Finaly found it. Had to delete both the file in "C:\Documents and Settings\<user name>\Contacts" AND the same one in "C:\Documents and Settings\<user name>\Local Settings\Application Data\Microsoft\Windows Live Contacts"
/ 
