It looks like the current implementation uses a central store when a frozen key is used. This would mean that the keys would never be garbage collected, correct?

I was looking at another WeakMap implementation here: https://github.com/drses/weak-map

It overrides Object.freeze like this (as well as seal and preventExtensions):

var oldFreeze = Object.freeze;
Object.freeze = function(obj) {
    Object.defineProperty(obj, HIDDEN_KEY, {
        value: {}
    });
    return oldFreeze(obj);
};

This allows it to put a key-store on an object just before it is frozen to give it the opportunity to be used in a weak collection.

This approach may be a bit iffy. The drawbacks are 1) every frozen object gets an object added to it whether it's used or not, and 2) if an object is frozen before the freeze method is wrapped it won't work. But a huge pro to this approach is keys are garbage collected.