As an update here are some links reporting similar behaviour sometimes by design, sometimes clearly buggy:
http://stackoverflow.com/questions/6867892/reducing-memory-usage-in-an-extended-mathematica-session
http://groups.google.com/group/comp.soft-sys.math.mathematica/msg/f95a9588b9803f54
http://forums.wolfram.com/mathgroup/archive/2011/Aug/msg00012.html

Summarizing here are some typical examples where Mathematica does not clear Module generated temporary variables:

1.
Result: x$NNN is not removed.
Reason: ¿ NDSolve stores some expressions referencing x$NNN in the system cache ?
Solution: Clear system cache. (Presumably this will happen on its own as the kernel session progresses.)

2.
Result: y$NNN and z$NNN are not removed from global context.
Reason: y$NNN and z$NNN appear in the module output and are thus referenced by Out.
Solution: Clear Out, or more systematically limit the History Length through $HistoryLength


3.Result: x$NNN is not removed from global context.
Reason: Definition of f is referencing x$NNN
Solution: Clear f.

4.Result:a x$NNN is permanently placed in the global context every time a is called.
Reason: Unknown. This appears to be a bug.  (Clear and ClearSystemCache[] do not remove the x$NNN.)

5.
Result: a$NNN and b$NNN remain in global context.
Reason: Unknown. Bug?


It would be very helpful if someone could explain the behaviour of 4. and 5. (and how to avoid it).

@martin:

The variable generated by Module are supposed to be temporary, i.e. they should be deleted as soon as they are no longer needed.

See the article you quoted:
(Note that the last sentence is apparently not true, since in the example provided the variable is not explicitly returned.)

Also note that Block and With are not suitable for what I need. (Local variables inside functions, which do not interact with existing global definitions)

@ Martin:
 The example you give acts as one would expect. Evaluation of that module leaves y$NNN and z$NNN in the global context because those are present in the output of the module (2 (y$NNN + z$NNN)).

If you set $HistoryLength=0. Mathematica will actually remove those temporary symbols, as they are no longer used.

Update:
In the example I gave, the persistent temporary variables are in fact removed if you clear the SystemCache. So it appears, that in that case NDSolve is storing some expressions involving that variable in the system cache.
But I have also encountered much more complicated examples clearing the system cache does not help. (I'll try to cook up a simple example)

Update example:

Compare:
With: