Just curious...
Could you post the name of these files, so we can try to search for them?
Not everyone has access to all of the files on the network...you could go into the 'connections' tab and remove the hosts when you can't find your files. New ultrapeers will be generated for you and you can try searching again.
Good Luck
Dan