Doug, there is a bug that if someone deletes you from their Friends list, you won't be able to send them private messages. However, these persons who deleted you, don't disappear from your Friends list.
It's a bug that's been reported several times now. As WGTalex says, friendships should always be mutual. However, in order for this to work, WGT must remove the bug described above. If someone deletes you from their Friends list, your Friends count should decrease by 1, and that person should disappear from your Friends list. Right now, this isn't happening.
Maybe you tried to send a message to someone who had deleted you from their Friends list? Take a look at that person's Friends collection to check if you can still see your avatar picture there.