If the tool is being installed on every run of the job, then I think there is something else amiss with your installation. I have several different automated installers (2 maven, 2 ant, cmake, etc.) which deploy to many different platforms successfully (including Windows).
I have a job that uses the elastic axis plugin to run a sample maven job on each of the agents using the specific maven version. It works reliably, and once that job has run, other jobs do not unpack the maven installer for that maven version again.
Are there any unique or special settings you're using to configure your agents?
Mark Waite