AVG could be blocking the return connection for POP3 from your mail server, can you check any AVG logs on the system? (I'd look, but I run the retail AVG, not the free version, and I'm not at home at the moment).
I'm not a fan of McAfee either. I dumped it when I discovered that the "firewall" was blocking the Remote Access/Remote Assistance setup I was testing on my home network, and could find no way to configure it to permit such access. I run Kerio Personal Firewall (http://www.kerio.com/kerio.html) as a last barrier into my boxes, behind the DSL firewall and MS ISA Server 2000. Much more configurable.
Hmmmm...re-reading your post. I'd say the AVG is misconfigured or broken, based on the error message you are getting POP3, Server Response: '-ERR AVG POP3 Proxy Server
Are you using the firewall beta product they advertise on their web site?