Okay, here goes from a bit of an Android fanboy.

To search your GMail, go into the GMail account you want to search, in your inbox, hit "menu" and select "search" and it will give you a GMail specific search box to fill. You can also see you GMail folders too. It's really a replication of your regular GMail experience on a PC or Mac.

In MS Exchange account you can do the a similar thing. Go to the inbox, press the search hard key on the front of the phone (upper right corner hard button?) and it will pop up a specific search box for that account. I just tried it on my MS Exchange push account. It will pull up matches as you type.

Your battery life is strangely bad. There might be some Incredible specific issues that can be solved but I don't have that handset. I found that with rooting (jailbreaking in Android parlance) and a custom ROM could do wonders for your battery life. Rooting will also allow for easy tethering. I just tethered my HTC Hero to my iPad for a quick Internet hit. (Screw the iPad 3G!)

The software issues you complain of is very unusual. I know a bunch of people with Android handsets and have not reported your issue. Do you have a bad handset, maybe? I would definitely search an Android forum. I use androidforums.com.

HTH!

__________________