Какие существуют стратегии кэширование запросов к Google Map?

Кэшируйте ответы геокодера в базе данных на сутки, скажем. Мы почти все ответы с Яндекс.карт кэшируем.

С прямым геокодированием просто: есть аддресс, есть результать в виде координат — это можно хранить в кешах ооочень долго, возможно даже в базе.
С обратным сложновато, тк все таки координаты могут немного отличаться, но если координаты в основном не меняются, то также можно эффективно кешировать. Если же координаты немного отличаются, то можно округлять, например до 10 метров ±, результат не должен сильно постарадать (можно протестировать).
С роутами ситуация похожая, те для аддресов как с прямым геокодированием, для координат как с обратным геокодированием.
Для кеша подойдет любое key-value хранилище, в часности memcached и ему подобные, зависит от обемов данных и места для кеша. Хранить как запрос-ответ, в принципе на любом уровне обработки главное чтобы можно было создать уникальный ключ (хеш) и дессериализовать полученный объект. Время хранения на вкус, вряд ли эти данные будут часто меняться, а если и будут, то врядли значительно.