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.