I came across a piece of news talking about KDE's Raptor. I didn't test it, but what I can tell from the screenshots and the more technical paper, Raptor looks really really promising. It's a mix of a menu, Deskbar and Quicksilver.
The most significant part that Deskbar doesn't has is that Raptor (such as Quicksilver) remembers what the user did in his/her previous sessions. That way the most likely item will be displayed in the center. I find this feature very useful, because obviously every user is different and that way the program adjusts to the user and not the other way around. In addition, someone suggested this feature on the mailing list, as well.
This feature wants me to make use of sqlite, again. The sad part is that neither the sqlite module nor Python 2.5 are blessed dependencies. Till now it's not too bad, because I can use Python's pickle module, but we'll get a problem soon: Firefox 3 stores bookmarks in a sqlite db. Furthermore, using sqlite, bug #468325 could be solved.
Update: I found a site that explains how Raptor finds the most applicable item.