...you don't need Vlingo. I downloaded Google Maps, and a Voice Search app popped up. It's Google's voice search. I put it on my home screen, and just use that to search or use the navigation, as they both just go through Google search and/or maps. If it doesn't appear in your app list, try changing the view to list view and back (or rebooting). If you don't want to root, just delete the Bing widget, toss the Voice Search app on one of the screens and move on (the only thing affected at that point that you would notice is the search soft key, which I never use).
Just wanted to say that this is the only answer I've found to getting Google to work as default without using voice. Downloaded and installed the .apk file and now Google search is default for the widget on my Galaxy S. Thank you so much for your help, hopefully more people can find this information and end their frustration!
My non-rooted phone has the Google widget and uses google search when using the Search button.
But there are caveats. Using either method for an initial search uses google but if I do any navigating in the browser it reverts to bing. Also, when I use the Google widget, it will appear to 'attach' itself to the top of the screen even though the touchscreen doesn't register it there (i.e. it no worky anymore) but pressing the HOME key almost always fixes that.
I'm having a little trouble successfully having the Google search icon appear in either my application list or able to create a shortcut. I have sucessfully downloaded the .apk file, copied it to my sd card and installed it using launcherpro. Please help me find it in the phone so I can put a shortcut to it in the application list and on my home screen. Thanks