Thanks for your comments. It is definitely worth considering garbage collection of classes. As you point out, keeping a "standard" map whose keys are Method objects will prevent the Class instance that owns the method from being garbage collected since a Method has a reference to its owning Class.
Using a WeakHashMap is a good idea, and probably the best way to go. By "mangling" a method name, do you mean including the method's parameter types (a bit like the toString() on Method)? The drawback with this approach is that you have to reconstruct (or retrieve from a cache) the Method each time it is invoked.