Looks like I'm going to try VLingo after installaing and trying a bunch of these similar apps. VLingo seems to more or less get my location correct and is doing a fair job of understanding me. It at least tries to do a search for things that aren't in my contact list. And most importantly it doesn't add that bleepin-a-bleep-bleep "+1".
I really wish "voice search" would just work instead. When I get a bit of free time I'm going to go to a Verizon store and start complaining to their technical support people in my area. If my original hypothesis is correct and this is a regional thing in the south east part of PA, a brick and mortar store might be the right place to start.
It's not a geographic thing. I have the same problem in Montana. To shed some light on the subject, the "+1" is an abbreviation for 001, which is the US country code. When calling a US number from overseas, you have to start with "001" or on some phones, "+1" will work. I believe the problem is that Verizon is assuming you are trying to make an overseas call when you dial "+1". That being said, I still have no solution to the problem. Maybe I will call Verizon and raise hell.