I think Valve disable baloo (understandable since you don't want file indexing while gaming). That's probably why the default KDE search will perform poorly. You should be able to use KFind which will work kind of like the Windows XP search.

Thanks. While looking up KFind I found FSearch. That's almost VoidTools Everything.