Credit to Android Central
Here's how to put Google search back on the Verizon Fascinate, and it takes just a third-party launcher and a single download. It's simple as can be and doesn't require root, and it adds one piece of functionality we were missing from our previous fix: You'll get native Google search and voice search back.
Here are your instructions:
* Download the Enhanced Google Search provider apk from the second post of this forum thread.
* Place the file on your SD card, and install it through your favorite file manager.
* In a third-party launcher (like ADW or Launcher Pro), put the Google search widget back on your home screen, if you like. It'll work now. Same goes for the search button. Again, you have to use a third-party launcher.
You'll still need to download Google Maps from the market if you haven't already. And while the phone's physical search button (or capacitive, we know) will now work with Google, holding it to initiate a voice search still routs through Bing. So we're about 90 percent there. (Update: See below)
Otherwise, we're talking no root, no muss, no fuss, and no waiting for Verizon to "fix" this when it eventually releases Android 2.2. I love it! [Android Central forums] Big thanks to namebrandon and Cory!
Thanks to Android Central for this wonderful mod.