There's the scout program for that. It searches contacts, calendar and conversations.

I suppose that adding search capabilities for bookmarks, apps and tracker-indexed data (also e-mails) wouldn't be *that* hard, but I personally have not so much interest in that, and anyway no time

Perhaps @nicolai (he wrote scout AFAIK) could do that in 5 minutes?