As far as I'm concerned, there are three critical things you need in a Geocoder service.
1. Global Coverage
Because when it doesn't have global coverage, it's basically means "America-only" and thus pointless for most of the world.
2. Multiple Matching
For ordinary humans, there's massive power in being able to just search for "1 Oxford Street" without listing any more details. From there, if it is a country-specific application you just change it to "1 Oxford Street, Australia" behind the scenes.
That results in a list of possible locations.
You show the results for the first result, and then a list of "Did you mean:" links for the other results. This lets the application do what people mean most of the time, while making it trivial to recover if it isn't accurate enough.
You can see the effect I'm talking about by running the example query here...
3. No usage limitations
Google Maps Geocoder can only be used with Google Maps. Fail.
I'm willing to accept a volume limitation like "You have to pay after the first 50,000 requests" but I can't accept a usage limitation.
I'm happy to report that Yahoo's new PlaceFinder service is the first free Geocoder that meets all these primary criteria.
It's global in scope, lets you control the list of results with paging, and doesn't limit the usage to any particular domain.
Now all we need is an Geo::Coder plugin for it.
Please write one for me Lazyweb