Sounds like Google desktop actually fits the bill quite well, you have to click on the Web, Web History, Gmail and Desktop tab one at a time but it does search in most of what you asked for.
I haven't found a perfect solution for myself but there are a number of tools nowadays that do search your collection of data in cloud.
Favs (OSX, iPhone)
It collects all your favorite items in a nuber of web services (Google Reader starred items, Delicious/Pinboard bookmarks, Facebook statuses, Twitter favorites, Pocket, Instapaper, etc.) and make them searchable in one place. I personally use this a lot.
Search your Gmail, Outlook Exchange (email, events, docs) and Twitter stream. It's quite helpful if you use Outlook at work like I do and find Outlook's search lacking.
Connects to a number of cloud storage (Dropbox, Google Drive, Amazon S3, etc.) and search all your files in one place.
A good place to look for these apps is through websites of the services they support. Many of those sites maintain a list of third-party apps that uses their APIs.