iPhone 4S keeps old numbers in Messages The numbers that are no longer in my contacts still keep popping up when I try to compose a new message. 

Why is this happening? Is there a way to purge the contact list so no already-deleted-contact remains?
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.