Yes it should work fine, I use Outlook Express 6 with AVG 7 Free Edition.
Two things that you could try and report back...
1) Download AVG 7 again and do a clean reinstall. If your problem comes back then try temporarily disabling the eMail Scanner. Does that make a difference?
(go into "Control Center -> eMail Scanner -> Properties -> "Disable Plugin -> Ok". To reactivate, Right Click and "Activate".)
2) Do you use a personal firewall (eg ZoneAlarm or Kerio)? It may be that your Outlook Express firewall entry is okay but your AVG firewall entry is incorrect?
(easiest way to progress this is to delete the AVG firewall entries then send a test eMail - the firewall should detect the traffic and prompt you to set the AVG rules back up)
RC
(PS ... what ISP / eMail service do you use?)