For permission to install programs:
If you have the user's permission, you can install any program they agree to, or do anything to their computer that they agree to.
For installing specific applications:
Check the EULA, if it says for personal use only, that limits businesses from using it -- that doesn't stop a consultant from downloading it and installing it onto a home user for their personal use only. If it says you can't distribute it, then each place you install it, download it from the website directly. If it's for single use only, it usually means that only one person is allowed to use the software at the same time.. if it's free software, this is almost meaningless, if it's purchased software, it means they're licensing YOU to use the software.. no-one else (unless you sell the license to someone else).
For licensing:
In most cases, when you purchase the software, you own one license. You may use this on only one computer at a time.. if you transfer it around to different computers, you must uninstall it from the previous computer first.. so unless the EULA says otherwise, you can install purchased software, do a scan with your license key, and uninstall it.
For removing spyware:
I heard a few things about it being illegal to decompile spyware for the purposes of uninstallation under the DMCA, but that's something that they'd go after the anti-spyware companies for, who are actually doing the reverse engineering.
As for the guy who phoned up ZA, he probably had a pirated copy of ZA, left by a tech on their computer... as long as you don't leave any of the programs you own behind, then you are fine. Install some free alternatives for them to use.