From what I understood, there is also a limit to the list of recent projects that you can access within Premiere Pro, Photoshop etc. Once its buried low enough on the list, it will be taken off the list since it has not been opened for a while. Usually if I want to locate a specific project file, I would make sure I know and remember which folder I have it and categorize it in a way that can help you easily find it and quick.
Like for example, I have a folder dedicated to a list of video projects I am working on with Premiere Pro and Sony Vegas. But I know what you mean, I feel Premiere Pro should be able to have a feature to search easily for project names you seek without having to locate it so I agree with you there. Its also convenient to know where is that file located like the Open in Folder feature. I will check my Premiere Pro later today to see if I can find the feature close to it. If I find something, will let you know.