[mjdwitt]

something ... which searches across the entire phone

You can actually use the default Google Search app that comes installed on most versions of Android. You just have to go into its settings and tell it to search more than just the web.

And as far as removing those default apps that you can not uninstall: since you already have your phone rooted, you can just delete or rename their process files and they will be effectively uninstalled.