It sounds like the code that passes the key to google is duplicated on your page.
look in the code for the page, you should see code similar to:
if you see that code more than once, delete the other instances where the key is not the correct one to use.
when you request the new api key is it different than the last one?
Are you using the site Domain or IP Address? you should use the domain.
The API Key is a hash of the URL you enter, if you are entering the same URL on 2 separate occasions, the hash will be the same, the algorithm used by google does not change.