BB Messenger-Contact not showing up

Ok... first the problem.
My one friend has a 8800, I have 8130. He is my only friend(long story) so he is the only one in my BB messenger contacts. We both are on Verizon as if that matters.
So the other day he(not to electronic inclined, but learning!)tells me that he lost me as a contact. So he re-invites me. No go. I delete him, re-invite him. No go. But I can start a conversation with him, im each other, but I'm not in his contacts. When he does re-invite me I accept, shows pending, but never goes thru.

Oh and both our status are set to available.

Things we tried:
He delete me.
I delete him.
We both delete each other at the same time.
Mind you every time we try this, after deletions, there are battery pulls.

So any ideas?