<p>Supposedly, it is possible to get this from Google Maps or some such service. (US addresses only is not good enough.)</p>

The term you're looking for is geocoding and yes Google does provide this service.
New V3 API
:
http://code.google.com/apis/maps/documentation/geocoding/
Old V2 API:
http://code.google.com/apis/maps/documentation/services.html#Geocoding