A feature or a tiny bug?

Search a file in Dolphin, delete it permanently (pressed Shift key) and repeat the same search and the deleted file will still shows up again, but the icon is neutral now.
Is the deleted file cached for some reason?

Is it btrfs file system with timeshift snapshots?

I guess the indexer (Baloo) doesn’t immediately update when a file is deleted.

It could be a feature? I know I’ve accidentally sent files to the trash and then soon restored them, a delay in deleting it in the Baloo would save it from needing to be re-indexed, but I’m just guessing here. You’d have to contact the developers to be sure.

Disable Baloo completely (Settings → Search → Disable all), then open Dolphin, search, and see what happens?

No, ext4 and yes Timeshift is enabled for root only (stored on home).

Yes, indexed for some reason, that’s what I thought as well and what you mentioned make sense.
When I close Dolphin and reopen it, that deleted file won’t appear in the search again!

@Masalababa timeshift does not include /@home per default settings. Unless you enabled it, it should not have x copies of your user files.

Try what @omano suggests. This should be a matter of Baloo still having it indexed.