Solución:
He encontrado la solución al problema.
Debe habilitar tanto la API de JavaScript de Google Maps, y la API de codificación geográfica.
https://console.developers.google.com/projectselector/apis/library
y
https://console.developers.google.com/google/maps-apis/apis/geocoding-backend.googleapis.com
Posteriormente el error fue RefererNotAllowedMapError en lugar de DeletedApiProjectMapError, pero eso se debió a que lo estaba ejecutando en localhost, y funcionó en el sitio real después de agregar el dominio en Credentials -> Domain Verification.
Solo para agregar a la respuesta anterior con una imagen (y esta solución funcionó para mí mientras aún permanecía en la máquina local), porque estaba un poco confundido acerca de la habilitación de la parte de API.
Simplemente navegue hasta: https://console.developers.google.com/projectselector/apis/library
Seleccione su proyecto (para el que tiene una API)
En el lado derecho, expanda la sección API de Maps y haga clic en “API de JavaScript de Google Maps” y en “API de codificación geográfica”.
En la página que aparece, debe hacer clic en el botón “reproducir” para habilitar la API
Entonces debería estar listo para continuar sin autorizar dominios y continuar trabajando en la máquina local.