TotalCommander works exactly as well as the Find function on a PC. It won't search databases like Contacts though, as the native PPC Find function should when it works. TC is free:
http://www.ghisler.com/pocketpc.htm
You might try running a program found in \Windows called welcome.exe. It simulates a post-hard reset routine, but causes no harm and can mend certain glitches in PPC operation by correcting registry corruptions of some sorts. Failing this, I'd do a full backup with Sprite then hard reset and rebuild databases and data (not program, but docs and stuff) files, but manually install programs.