Hmm. A couple things going on possibly. The Geo locator relies on Google to return the valid positions of the addresses. For this need, it must have addresses that are properly formatted to be transferred to the api call. One thing that causes problems is carriage returns within the address - for some reason the result never seems to come out properly when they are present. Another possibility is that you may not be using the correct key for your geolocator - so double check that everything is fine from that perspective.

I've had quite a bit of luck getting geocoding to work, generally 85% of the time for US addresses, and 75% worldwide (For most of the general world that is). One thing I have noticed is that Google does a poor job of handling postal codes for most of the world. Often, if the postal code is removed, the coordinates come out properly.

Two notes that may help you in the near future - In the upcoming release Custom Queries will be extended to support not just Custom Selection of points, but custom insert / update / delete statements as well so that you can manage your point data (and more importantly geo-code it automatically) even when it is in an external table. Additionally - the handling of Geo-Coding is being extended to provide more information about when the points are being coded, and more importantly - any additional information that the service can provide as to why the addresses are failing.