Are your contacts being stored in the cloud?
If you force kill messages app and then reopen the app do the names still show up?
I seriously doubt I'm the only one experiencing this. When I delete a contact and search the name of that contact in iMessage, their name and phone number still shows up. Glitch or just software fault?
Messages app stock piles a sort of auto complete index.
So you can even text someone, or a service, and without adding the contact, it will remember that again in the future.
I don't know of a way to wipe that index.
Or at least from my experience, that's what it seems like is happening.