Try something like Ipcop with Copfilter.
www.ipcop.org
www.copfilter.org
Ipcop is a firewall distro designed to convert a older pc to a firewall/router. Copfilter is an add-on available to offer scanning of web and E-mail traffic.
Seriously though, what you describe is a nightmare. It sounds to me like your users are their own worst enemy. Nothing you put into place at the router level will be able to stop users from doing stupid things and infecting themselves.
IMO, if you are going to charge a fee to keep their machines virus free, do yourself a favor and don't offer a guarantee! It will cost you way more in time saving users from themselves than you will ever make in fees.
HTH
Dave