If using the Google Geocoding API or another online source is your preference rather than local options, I'd suggest looking into the Tor Project (easily installed through the bundle called 'the Vidalia Bundle').
Tor protects you by bouncing your communications around a distributed
network of relays run by volunteers all around the world: it prevents ...
the sites you visit from learning your physical location.
Along with injection of random addresses and using ssl (https) to encrypt communications to their endpoints (make sure you're also doing this), I can't think of a more secure way to geocode remotely. Whatever geocoding service you're using won't ever be able to identify where the requests ultimately came from, and with https no one else will, either. Note: don't use a geocoding service that requires an api key for this, or you'll no longer be anonymous. (Google doesn't require an api key anymore).
A side 'benefit' of this procedure is that you'll no longer be restricted to any number of geocoding requests, as your requests will look like they're coming from multiple ip addresses. However, I do not recommend or endorse abusing these lovely free APIs! Rate will still be limited if the API limits rate (though the speed of transmission using Tor is quite a bit slower than connecting directly).
Case study in Python -- Once you've installed the Vidalia Bundle and have the proxy running on 127.0.0.1:8118 (the default), in Python 2.7 or higher you can set up an https urllib2 proxy using:
import urllib2
proxy = urllib2.ProxyHandler({'https': '127.0.0.1:8118'})
opener = urllib2.build_opener(proxy)
urllib2.install_opener(opener)
response = urllib2.urlopen("https://maps.google.com/maps/geo?q=Los+Angeles&sensor=false&gl=us")
Note that urllib2 proxies don't work with https until at least Python 2.7 or so, so this method only works with recent Python versions. Make sure you've got 'https' (not 'http') in both places in the example above. I've only tested it with Python 2.7.1.
Vidalia changes your identity / apparent IP address origin every 10 minutes, but if you run into slow rates or other problems (quota exceeded errors), or if you are especially paranoid and want to change your identity more frequently, you can change your Tor identity using the python code here (slightly modified below). You'll need to change the Tor password to a static one (rather than a randomly generated one) by entering the Vidalia settings. Might also need to restart Vidalia after all changes.
p = "MySuperSecurePassword"
def renewTorIdentity():
success = False
try:
s = socket.socket()
s.connect(('localhost', 9051))
s.send('AUTHENTICATE "' + p + '"\r\n')
resp = s.recv(1024)
if resp.startswith('250'):
s.send("signal NEWNYM\r\n")
resp2 = s.recv(1024)
if resp2.startswith('250'):
success = True
except:
success = False
return success