Nope, you're not doing anything wrong.
Unfortunately, enforcing tight limits on the Google Geocoding API, also called "Server-Side Geocoding", is Google's design. If your app needs more than 2,500 Server-Side Geocodes per day, then you'll need to upgrade to their Google Maps API for Business product.
Hold on, it gets worse.
If your app's server IP address is shared with other apps, that 2,500 request daily limit applies to ALL of them. This includes apps that share the same server IP address as you, but don't belong to you! This can be a common situation with any PaaS, like Google App Engine or Heroku. So, even if your app works flawlessly today, there is no guarantee that it's still going to work tomorrow.
In the article, "Geocoding Strategies", Google indicates the solution is to "almost always" use "Client-Side Geocoding" via the Geocoding Service, part of the Google Maps JavaScript API V3. The primary reason is that limits are enforced per user, per session. Requests like this shouldn't run up against quota limits unless you're executing geocode batches on the client (not a typical use case).
One golden nugget from the "Geocoding Strategies" article: Design a page that takes user input, calls the client-side Geocode
service method, then passes that information to your server app where it can be processed, and hopefully cached. This is FAR from ideal, but if upgrading to Google Maps API for Business isn't an option, it might be the only way to go.
Good luck!