iPhone --> Android text messages = garbage characters

When I send a text message to an Android user, the result is completely unpredictable. Sometimes they go through normally, but I'd say about 50% of the time, the Android user receives some kind of garbage characters and a partial message. For example, I wrote an entire paragraph just a couple minutes ago, ending in the word "those." My friend responded:

"This is the text I got: Ԁ΍Єthose."

One of my friends refers to them as "hieroglyphics." Whenever one of my texts comes through as unintelligible nonsense characters, she writes back "sorry, hieroglyphics again."

I am not doing anything special with these messages. They are not sent with special fonts, emojis, accent marks, URL's or any other encoding. It doesn't matter whether they are short or long (it can happen to a 50-character text as easily as a 500-character text). It doesn't matter whether I type it on my phone, dictate it using Siri, or type it into the Messages app on my computer. The result is the same: about a 50% failure rate. Sometimes, the messages just don't through at all.

Of note, NONE of these users have recently changed phones. None have migrated from iPhone to Android; they are long-term Android users. I have had my iPhone 5s for a little over a year. Importantly, these "hieroglyphics" messages are all being sent as text messages (green bubble), not iMessages (blue bubble).

ALL my text messages to iPhone users go through (usually as iMessages).

I have tried soft-resetting my phone. I have tried resetting the network settings. I have tried updating the carrier settings. I have tried getting my friends to try all of those things on their Android phones. I read something about a full message queue affecting the apps, so I had my friends go though and delete a lot of their old text messages (I delete mine constantly). NONE of these solutions have helped.

Also of important note, sometimes my messages are simply never received at all. I've never RECEIVED a hieroglyphics message, but I definitely have had times when I simply do not ever receive a message that an Android user sends me.

Thoughts? This is really aggravating! I use text messaging a lot at work, and some of my messages are very time-sensitive. I'm beginning to consider text messaging an unreliable communication medium!

Thanks,

-- David