I think I have found one:
They have several versions and I tried so far the professional trial. However the free version seems to be sufficient for me: http://www.gaviri.com/gaviri-basic-searchos.php
It uses about 20mb on the usb stick and indexes all "popular" files. Even thunderbird stuff - this is nice when you use portable apps in general on your stick. Upon installation, make sure not to install it onto the harddisk.
I did test this today at work with an install on the stick and then I setup at home a winxp in a vm and run the .exe on the stick and it works... files are indexed despite them being now assigned another drive letter. I think a unique ID for all the devices is used to determine where files are.
I'll test it more in the next few days.