I have found the solution to the problem.
You need to enable both the Google Maps Javascript API, and the Geocoding API.
https://console.developers.google.com/projectselector/apis/library
and
https://console.developers.google.com/google/maps-apis/apis/geocoding-backend.googleapis.com
Afterwards the error was RefererNotAllowedMapError instead of DeletedApiProjectMapError, but that was because I was running it on localhost – and it worked on the actual site after I added the domain in Credentials -> Domain Verification.