Well, I'm not an expert on the proxy stuff, so I'd rather wait for Lukor...
However, are you saying that even Outlook 2003 didn't work? Did you use the avast! Outlook/Exchange plugin, or the Internet Mail provider? I'd say it should work with the Outlook plugin, because there's no proxy involved there.