How to best prevent malware problems?

Most of our customers have small networks with just a few PCs, while others are single-user.  Most all are running Win7 Pro.  We install Norton internet Security on each one and keep it current.  Many are in rural areas of the country, and most get their internet connectivity from local DSL providers, while a few are on cable or satellite.

The problem is that a few of our users have constant malware problems, where I have to run Malwarebytes and Spybot on a regular basis, often cleaning up dozens of infections each time.  Recently it got so bad at one location that I had to reformat two PCs just to get them running right again.

I have never understood why Norton seemingly lets so much get by for these customers.  I've tried others in the past, such as Trend Micro and McAfee, with the same results.

I'm wondering if there is a better solution.  I am 'aware' of hardware firewalls, but there are many things I don't know.  Do they do a far better job of preventing these infections?  Are they affordable for a small network or single-user computer?  Are they easy to maintain and keep updated--assuming that is needed?  Do they tend to block legitimate work that the user needs to do, or have other quirks?

Or maybe there is a completely different solution that I don't know about.  Any clear, detailed guidance based on experience would be greatly appreciated.  TIA