There is a limit of 2500 requests per day per requesting IP. When using geocode on appengine,application in GAE share those quotas with any other application in GAE that happens to use the same API since all those applications are served from a limited number of google IP's making the API useless. I have been many days i unable to use geocode as i get error message 'You have exceeded your daily request quota for this API' when i did not even do any geocode query for many weeks already.
I checked internet, few others users are facing similar issues
I can't move the geocode the client side, as my application need to do geocode on server side.
You'd have to pay for the Service then, give the googles a call and they'll make you an offer. I was in a similiar situation and what i did is, i cached all the result, most of my calls where redundant anyways.