If you delete a contact when you are disconnected from the backing service, the contact will re-appear the next time you connect. Make sure you are connected to the account you are deleting a contact from before attempting the delete!
Deleting a contact
Right click the contact in your contact list and click Delete.
