Weird issue with contacts

[s4boost]

When I go into my messages app and hit the "new message" icon and start typing a name, it shows me contacts even if I don't have any in my phone. For example, this girl named hope changed her number to the 830 number, so i deleted the 689 number, but it is still there. Also, I turned off iCloud so there were no contacts in my phone whatsoever and still I could see both listings. If i click on the 689 one to send a text to that number, it shows the number in the "to:" field, not her name. Anyone else experienced this?

[Cer0]

In your contacts at the top click groups and see if you got more groups. Like I used to have this issue when I had my icloud group/phone group and Mac group. When you change it the Mac group never changed just the icloud group.

[s4boost]

Well the weird thing is, that's the only place I see the duplicate... if I search for a contact in the messages app to begin a new conversation.

If I go into the contacts app, the only listing I see is correct one. And the only group is the iCloud group. So I'm completely lost.

[s4boost]

It's kinda like when you type in an email address and it stores it in the cache. I literally have no contacts, but when I start typing a name in the messages app it shows the contacts.... Any suggestions?