After reading the post by Seif Lotfy about the design of an interface that makes it easy for users to access files without the need to explore their file system, I have created a mock-up of the interface that I would like to use.
Obviously, the idea is not new (which is part of the appeal that this approach would have) and the main work would not have to go into the design but the underlying search algorithm.

Finding vs. Exploring

As Seif said in his post, exploring the file system (or bookmark hierarchy or application menu...) is not an ideal way of finding the documents you are looking for. But exploring the application or places menu to find the search application to then search for the document is also not the best way to handle this.
So, how can this be made easier? By using an intelligent search, something very similar to the ubiquity project. A search that knows that "google world cup 2010" means a google search, but "world cup 2010" might be a search for a file or something else, that "gimp" means simply launching the application and "email this to marc" would suggest a list of marcs from your contacts and launch the default email application with a new email to that contact and the current clipboard as the content or attachment. (This is the way ubiquity does it if you use googlemail, really cool!)

First question: Where to put that search?

The search (if it worked) would replace the file browser (when the file browser is used to explore the file-system in a search for a file), it would replace the desktop as a file and launcher holding place, it would replace the current three menus "Application, Places, System".
And it should also be obvious that this search is the place to start.
To me the answer is clear. It should be at the center of your view, large, and free from any clutter: just like the google interface.
So here is my first mock up of the desktop.
(Note: this is the desktop, not an application in front of the desktop).

And to demonstrate how such a search could look like, there is another mock up that shows the autocompletion or tips

And also the result of a search, if you actually hit enter or press the search button. The results should be ordered by a mixture of relevance and last accessed. Maybe even taking into account what the user did some minutes ago and so on (powered by zeitgeist

Note that the search should be always in reach, so, since it replaces the three menus as the standard way to get into your computer, there could be a shortcut to the search at the menu position (as you can see in the pictures). Alternatively, there should be a keyboard shortcut which gets you to a clear desktop and places the focus on the search field.