I have a contact, and I can’t have encrypted messages with it.
It says: “Personal key has not being verified yet”. When I see in Details, it says: “Verify the personal key”, then I press “Accept”. And it says “Failed delivery”.
I don’t know. But this contact add me in a Kontalk conversation when I didn’t have it in my cellphone contacts list yet. Then I added this person, but it keeps happening the problem with the unverified key, and the impossibility of encryption.
It might be useful to know that an issue with key trust was fixed recently, it will be included in version 4.0.1 which is due very soon. It’s most probably related to your issue.
In the meantime, there is another thing you can try: delete all of the app’s data from Android system settings > Apps > Kontalk > Clear data. Note that it will reset Kontalk preferences and reset key trust settings (you’ll have to accept all the keys again), but your account will not be touched.