Sorry if this is no help but I have the exact same problem with a client. I did his site around 18 months ago and he rings every month to inform he needs a new API key because his Google map has stopped working. I used the same extension you have too. Oddly, no other client has the same problem so it must be a Google problem rather than WA.
Warrington Website Design