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.
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.