Re-adding a deleted Contact does not work

Steps to Reproduce:

• add each other as contacts
• delete contact on device A
• try to add contact back on device A
• device B will get an error message and not add anything
• device A will have contact from device B back

However, on both devices, the users see each other as offline and can not exchange messages.

This issue is related to issue #2.