I have a similar problem with Outlook 2003 - the antivirus is not running for Outlook. Icon on taskbar says "Avast on-line scanner: 7 providers total, 6 running." The one not running is for Outlook/Exchange. Anyone have any help on this?
Make sure the avast plugin is not disabled into MS Outlook:
Outlook 2003 > Help > About > Disabled items
Outlook 2000 > Tools menu > Options > Other > Advanced Options > Add-In Manager.
As reported a lot of times, the message "The provider is waiting on the subsystem to start" will be shown there until you open MS Outlook.
The plugin will be enabled automatically after that.