Does it block all .exe's? You could always try malwarebytes and Spybot search and destroy. Both free and very effective.

@ Sio: have you ever tried ultraVNC? You can create a one-click install that doesn't write anything to the registry. It might be useful if he can't install anything...