A large number of people on this and related posts seem to be misunderstanding the problem. The issue raised is that the iPhone does not delete the name and/or number to which text messages or iMessages have been sent. This is not a problem related to Spotlight Search. That is easy to fix and has been explained on here several times. Go into settings/general etc and uncheck "messages" and that does the trick, leastwise it should.
The problem here is that when you start a new Text message or iMessage (NOT an e-mail), the system pulls up a list of previous addressees not just from your current Contacts. For example, you once had a Contact called LS Dancing School but your kids now no longer go there, but you had sent the school text messages in the past. Now that your kids don't go there, you have deleted LS Dancing from your contact list. This has been backed up and synched with iTunes on your laptop several times. However, every time you send a text to a contact beginning with "L", up pops LS Dancing in the autotype list!!!
Apparently it is not possible to delete these old contacts from the autotype list. Whilst this is only irritating for many, it is a MAJOR SECURITY FLAW for the business world. For example, any contact with companies by text in the past, can be shown up this way. If that was unauthorised, or something similar, then there is no way of stopping that companies name showing in the autofill list thus recealing past contacts.
It seems that the only thing to do is a factory reset. This simply deletes all no-system data so you have to start again - but be warned, a back-up/restore will re-instate the problem.
I love my iPhone but this is a serious flaw which Apple seem to be ignoring. If they don't fix it I will end up with a Samsung and Android which would be a shame.