I've already implemented a subset of this. It is only based on two sources of information:
1) active editor
2) other open editors
The file open in active editor gets highest possible priority.
Other open editors get priority below that.
Also paths leading to something with raised priority will automatically have the same priority.
This results in a searching order that always searches the active editor first.
Then it searches all other editors.
Then it searches in directories "around" the active editor.
So that does already do your points 2..4
also 4.b (the projects containing other open editors next)
Since I'm not using infos on project dependencies or working sets, it doesn't do 5.
Also doesn't do 1 as I hadn't thought of that but it seems like a good idea.
Another idea might be to use SelectionService to listen for selections and remember the last X files visited and search them in order of most recent first.
What I've implemented is a helper data structure that tracks priorities for a finite set of paths in a tree-data structure. It is very easy to implement different priority assignments on top of that.
I also considered a different algorithm based on name similarity. Essentialy keep a set of interesting paths and use some algorithm to quickly compute a score for any path string based on how similar it is to any of the paths in the set.
What I got now seems already to work quite nicely though... You can all play with it next week
Another idea... if mylyn is available, maybe the implicit degree of interest model would be an excellent way of prioritizing the files to search in.