Also, are most of your requests coming from unique users, or do you see lots of users making repeated requests over and over? Maybe you could limit the number of requests for a single user. It sucks for them, but it allows you to implement a cap and affect the least number of people possible.

Are there any features of your product you can offload to other services? For example you mentioned directions -- why not link to Google Maps itself and let them handle that? (This might not be an applicable solution because I haven't studied your product to see how it works, but you get the gist.)

Is your code written modularly? Ideally you won't have to port all your code at once in some gigantic all-or-nothing rewrite. You can simply move one component of your code at a time to a free or open-source alternative to Google Maps. This could reduce your burden chunk-by-chunk over time until it's manageable.

Another avenue is to increase your revenue. Easier said than done, I know, but perhaps you could request payment/donations from users, or at least for repeat users. Or maybe you could reach out to the conferences on your site and see if they'll sponsor you.

Finally, I don't know anyone at Google, but it can't hurt for you to try to look up the right people and send some emails. I'd start with their developer advocates. This is a shameless plug, but I started a forum on my site (https://IndieHackers.com) recently as a place for founders to help each other out with problems just such as these. Can't hurt to post there and see if anyone has advice or connections at Google.

Good luck, sounds like a tough position to be in! (By the way, your site is awesome and it'd be very cool to interview you for Indie Hackers.)