I apologize for even replying because I'm a computer dummy, a real rube, but I was just having strange problems in my e-mail program, Outlook Express. Took a while to find it.
I was thinking for you: have you tried setting up one of the system's computers with Outlook Express e-mail instead of Outlook, to isolate whether it's a System problem, an Avast problem or a Program problem?