I deleted some contacts but in messages when I start typing M initial it will for ex show up Matt even though I deleted it.
Try resetting the keyboard dictionary in settings, general, reset. That may clear it out.
i know my contacts sync to icloud, but i deleted it and it backed up to icloud so it is erased on all my other devices! eh no big deal i guess, but it is wierd.
not sure; but did you also deleted all communications in Message ? Or any eMail still around. I think it not only search in contacts but also recent communications.