iPhone 4s text messages still appear in iPhone search results after being deleted
The messages are still stored in a cache database, with a field "removed yes" or "removed no", speaking in easy terms.
You can get rid of these, if you really have to by syncing your phone with iTunes.

If that doesn't fix your issue you can create a back-up and restore that backup.
Restoring should clean the cache databases and making a back-up first makes sure you get exact the same version back as you had previously.

However, I don't know if you use spotlight often -> I just disabled many results from appearing in Spotlight.

Settings -> General -> Spotlight