[Brian]

Do you have WiFi turned on? Location Services, the part of the iPhone OS that tells OmniFocus where the phone is, is able to much more closely determine your location if WiFi is enabled. Without WiFi turned on, the phone is seeing which cell towers it can talk to, how strong the signal from each is, and picking a location that matches.

Since cell towers have a fairly large area they can talk to, Location Services can't be as sure about where you're located. Since WiFi has much smaller range, if the phone can see a given wireless network, it can make a much more precise assumption about where you're located.

Did you include the quote marks when you set up the search in OmniFocus? When it comes to business searching, we're submitting the text you specify to a Google business search. When I headed over to maps.google.com and submitted the following two searches, they returned very different results:
"Lowe's" OR "Home Depot" 98119
vs.
Lowe's OR Home Depot 98119
(98119 is the zip code our offices are located in.)

The search with quote marks is telling Google to look for businesses specifically named "Lowe's" - other text strings will be ignored. If the store you were looking for was entered into Google's database as 'lowes', it would be ignored from the first search but included in the latter.

Does any of that help?