I was hitting it all the time until I got the Verizon combo case/holster. Any case with a raised lip the entire way around will prevent you from accidentally hitting the search button. That would include cases like the Verizon combo case/holster, the Verizon silicone case, the Body Glove case and the Seidio case.
Bingo. I've encountered the problem less frequently since I installed my Seidio case. As for "holding the phone differently," the problem largely disappears (I've found) if I grasp the phone slightly higher on the body or holding the Droid in my left hand. (Being a southpaw that's difficult for me since I use my left hand for the swype keyboard, but I suspect others may find it solves the problem.)