Damn if it didn't sneak up on me, or maybe I was just oblivious, but del.icio.us now supports search on your own set of bookmarks. And of course, since it's a RESTful API you can do all sorts of useful stuff straight from the address/URL bar in your browser.
Ryan Tomayko has already put together a nice collection of del.icio.us shortcuts for your entertainment.