I’m adding a second answer on this question, because I don’t want to remove the back and forth we had via follow-up comments on my previous answer.
But I recently came across some information that directly addresses your question and so I wanted to share. I don’t know if you are aware of this, but during the Google Maps API Office Hours May 9 2012 Video, Chris Broadfoot and Luke Mahe from Google discussed this very question from stackoverflow. If you set the video playback to 12:50, that is the section where they discuss your question.
Essentially, they admit that it is a bug, but also add that they don’t really support use cases that involve creating/destroying successive map instances. They strongly recommend creating a single instance of the map and reusing it in any scenario of this kind. They also talk about setting the map to null, and explicitly removing event listeners. You expressed concerns about the event listeners, I thought just setting the map to null would suffice, but it looks like your concerns are valid, because they mention event listeners specifically. They also recommended completely removing the DIV that holds the map as well.
At any rate, just wanted to pass this along and make sure it is included in the stackoverflow discussion and hope it helps you and others-