In the end there were only two candidates left: ShrinkSafe from dojotoolkit and jsjuicer. So I tried both of them against prototype.js which I happen to use on many projects and is actually quite large (96K!).
The results is the following:
unicoletti@ziggy ~/bin $ll prototype*
-rw-r--r-- 1 unicoletti unicoletti 71758 2007-05-31 17:27 prototype-jsjuicer.js
-rw-r--r-- 1 unicoletti unicoletti 68004 2007-05-31 17:27 prototype-shrinksafe.js
-rw-r--r-- 1 unicoletti unicoletti 96046 2007-05-31 17:26 prototype.js
And the winner is: ShrinkSafe, even though it a little slower and more hungry on resources, because to its Java nature.