Re:CD Offline (Score 1)

Maybe CDCollect (http://cdcollect.sourceforge.net/ - Gnome) or cdcat (http://cdcat.sourceforge.net/ - Qt) as they both feature searching, though I don't know whether they'll fit for you (and I didn't test them extensively).

I'm looking for one too, that truly supports Unicode filenames on Win32, and still searching...