Agreed with Seph, depending on the country that this is taking place in, it can be a privacy issue and may be against the law. As for weather or not it is technically malware, most AV software will pick up a number of “free” keyloggers as malware. They may not clean/delete them, but will certainly alert the user or admin about it.
Also if you do not have an acceptable use policy in place stating that “computer activity will be monitored and users may be held responsible if they violate policy…” yada yada yada… Then it could come back an bite you in the arse. I know in most European countries, user’s personal privacy is a huge thing and it is against the law to implement such monitoring behaviors without the user’s consent. The US, it is certainly more of a gray area.