How to clear iPhone's concact cache for text messages?
This has been FINALLY fixed in IOS 7. Now you can remove contacts from this cache.

As soon as the unwanted contact pops up while you're typing in the "to:" field, you can tap on a little "i" (probably for "info") icon on its right, and have a menu appear where you can remove the contact, or add it back to your address book if you feel so inclined.