This is actually expected behavior. The messsages are deleted from your device, but not the history of your device. If you want to remove those deleted messages from appearing in Spotlight, you'd have to restore your iPhone and set it up as new, but it will happen again when you delete other messages.
This is not a bug, its just the iPhone keeping history of things. If you tap the entry in the Spotlight search, it more and likely won't show up anywhere on your iPhone because it was deleted from your phone.
Its like if you cut yourself and it heals and there's no scar. There's no evidence of it on your body, but you remember it happening. Same thing with your phone