I have the same issue.
I had an iPhone 4S (and no other Apple devices that were registered with iMessage... it was the iPhone only). I turned off iMessage in the settings, and turned the phone off.
When people from iPhones texted me, it would send as an iMessage, and immediately fail, despite having turned iMessage off on my end. After communicating with them for a while, the convo would switch to texts.
However, days later, it would again attempt to send iMessages to me.
I've read numerous reports about going to your "Support Profile" and unregistering your devices (as suggested above), which I did, but I don't think that helps at all. I believe that site is just for warranty purposes. I've seen nothing about unregistering iMessage on that site... just unregistering physical devices. It did not solve the problem. I'm not sure why people keep saying to do this.
After more research, I've read it could take "up to a month" for Apple to un-associate your number. Much like aristrobrat has stated.
If others have know of a solution, please post. Trust me, I turned iMessage and Facetime "off" in the settings. In fact, I once turned it back on, and then turned it back off just to make sure everything was registering.