Not in the US, it's not. There have been many successful wrongful termination lawsuits bright about against companies that had no written policy in place. Not only for installing computer software but for just about any job-related activity you can imagine. Even if a policy is common knowledge and assumed to be understood by everyone, if it's not in writing, it doesn't exist as a legal reason for firing. Your country may have different laws but if the OP is in the US he has a good case.
I'm not surprised a law firm would think it could get away with such behavior, though. I once worked for a liquor manufacturer whose legal department is bigger than most entire companies. The legal department asked me to make copies of a commercial package on each PC in their department even though we only had a license for one PC. I pointed out that fact and they told me, "That company won't try to enforce the license. If they do, we'll keep them tied up in court so long, they'll go out of business trying to pay the legal fees." God bless lawyers!
