I briefly switched from an iOS phone to an Nexus 5 and had the same issue. For other reasons, I switched back. A colleague of mine liked the Nexus a lot and made the switch after I did. He has been fighting this for months. Everything works properly for a while. Sometimes, several weeks will go by. Then, out of the blue, my phone tries to send the message to him as an iMessage. It's bizarre and frustrating.