Lost some file index information

I seemed to have lost some index information on one of my portable hard drives.

Windows XP Explorer displays the directory (folder) name as if the file was there, but when I try to open it, there is a long period while it searches and then finally I get a message that the drive is not formatted and do I want to format it.

There doesn't seem to be a pattern to this index information loss. Sometimes I'm able to open a folder that contains sub-folders and some of these sub folders can be opened and some can't and trying causes the 'want to format the drive' message to appear.

I've tried retrieving these 'lost' files using PC Inspector and Recuva, but neither can find any trace of these files or there content either.

Are they gone forever or is there something I can do to at least retrieve all or some of the data content? :cry

Of course, Windows Explorer won't let me delete the folder, since it can't find it. So it remains listed in the Explorer file display (which is why I have no idea when the 'contents' went missing). I haven't tried to open some of these files in months.

Thanks for any help (or answers).