Recently Google changed it's policy on the use API keys. You're now supposed to no longer need an API key to place Google Maps on your website.
And this worked perfectly. But now I have this map (without API key) running on my localhost, which works fine. But as soon as I place it online, I get a popup saying that I need another API key. And on another page on that website, Google Maps does work. Could it maybe have something to do with that the map that doesn't work have a lot (30+) of markers on it?
Actually using an API key wouldn't be a very nice solution to me, as this is part of a Wordpress plugin used on many websites.
Sounds like you're running v2~ time to upgrade, or get a key for the domain you want to run it on: Google Maps V2 API Key Request