EVERY time someone calls with this issue, it is fixed with the click of a button that deauthorizes their iMessage token.
This is false. I just called 1-800-MY-APPLE (details in my reply to GP) and they said I had already deactivated iMessage for the number and that I needed to tell all of my friends to delete their existing threads with me. And then even that did not fix the problem.