It is not a leak if you have removed all references to it. If you're clearing out your map entirely, then it's not the source of a leak. You should consider the fact that the JVM chooses not to GC tenured generation very often as irrelevant to you - all that matters is that you don't have a reference to it, so the JVM could GC it if it wants to.
There are different strategies that JVMs can use to manage GC, so I'm speaking in generalities instead of specifics here, but GCing tenured spaces tends to be very expensive and has a high impact on the application, so the JVM chooses not to do it often in general.
If you're looking at the amount of heap space used, you'll see a sawtooth pattern as items are added and eventually collected. Don't be concerned about where the top of the sawtooth is, be concerned about where the bottom is (and how close to the maximum amount of heap space available that is).
One way to test if it really is a leak is to load test your app for a long period of time. If you have a leak, the base amount of memory that your app is using will go up over time (the bottom of the sawtooth). If you don't, it will remain constant. If you do have a leak, you can use a profiler to help you find it.