The problem is that cities have multiple names. For example in Minneapolis, Golden Valley is a suburb but people swap the names to suit their needs. So even though Golden Valley is a subset, the simple radius search can still be "honest" while appearing to stretch the radius. And don't even get my started on jobs that are 90% travel!
Would you say that requiring an actual physical address for each job on the site is feasible?
If I'm searching for a job, I've usually got a max commuting time in mind. Some towns are closer, but take longer to drive to because there's no highway leading there, or no train. Some are very far, but the train goes there, and so I'd consider the commute.
So, when a job ad has an address, that's what I'm thinking about when I see it: commute time.
So, I'd say that "good geographic search" == an honest one (that is, give me the results that are actually within the radius or area that I specified).