Hi
Send the people you are having problems with an e-mail on you Android asking them to send you a message.
When you receive it on your computer, use the add to address book option in your e-mail program to add the address to your address book.
If the new one works delete the old one.
Mike