This is probably over the top. But why not mirror those file names in /dev/shm/ (memory) and search against that instead? Ex:

# create dir structure

find /media -type d -exec mkdir -p /dev/shm/{} \;

# create file structure

find /media -type f -exec touch /dev/shm/{} \;

Then search /dev/shm/ for your files.