Why not use IMAP connections instead of POP? that way your users can monitor the junkmail folder AND use the LearnAsSpam folder as well.
Outlook Express and Outlook handle IMAP reasonably, although Outlook 2000 is a bit ropey (but usuable)
I presume you have got the RBSBL and DNSBL rejection on, no catchall, and not using fetchmail? Also you may well be getting spam through your MX backup email server.
A far less effective alternative is to use local email client rules to move tagged spam into another folder, but you can't train the Bayes table then.
I have clients receiving 100s of spam emails a day (often 70-90% of the total), and by using the techniques in the first and second paragraphs they are all "managing" it fine.