It's not just you.
Some people like Windows search, but it's not the best choice for me.
Try FileLocator Lite (aka Agent Ransack). FileLocator Lite - Free File Searching Utility
It's free, easy to use, and doesn't depend on indexing.
I don't use USB drives, so I can't comment on that performance.
I prefer a vanilla system as much as possible, but this is one utility i recommend.
edit: 4wd beat me to it !