So, geocode in the browser and then send the geocode to do your lookup. We even allow for caching, as long as you're going to display on a Google Map or Google Earth. Caches can happen in the browser or server side.
A few additional things to think about:
1) Cloud computing services often share a range of IP addresses. If you're running on AWS or Google App Engine or any other cloud computing service, you particularly want to do client side geocoding, as you may be running quotas parallel to other apps.
2) Some mobile networks share IP addresses as well. That can cause problems for your client side software, as lots of people on their smart phones are looking at your map. If you anticipate heavy mobile use, you might consider having a server-side back-up as a fail-over. Try to geocode and if that doesn't work, send the address to your server for http geocoding.
3) If you're still running into problems with quota, you may consider a Maps API Premier license. Check out http://maps.google.com/getmaps for more information on the differences and to get started.