iPhone 4S keeps old numbers in Messages
Assuming you have iOS 7 (now) I can provide you the steps on how to remove Recent contacts in the Messages.app.


Open Messages.app
Start composing new message
Once the list starts showing up, press the blue 'i' icon next to the number.
Press the redline Delete from recent
You're done, repeat these steps for the contacts you don't want to show up anymore.


EDIT: Community bumped this thread up making me answer it because I never check the dates. I hope I can still help anyone  out with this answer.