Yeah, that's a little weird isn't it?
I don't use JRemote, but I've played with it several times. I recall that there are two places to search. One that's inside each category. Then another "global search" that's outside all of the categories. I think it's in the side bar, under the icons for audio, video, etc. Go out as far as you can and it should be in the side bar. That search is relatively global and should be closer to what you want.
Brian.