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.
Although, if the problem is Outlook Express, the Internet Mail Provider is an avast! resident provider and it is not just the corresponding service. If you have Internet Mail running and stop the "avast! Mail Scanner" service, you disable the scanning of e-mails, but you don't turn the provider into "stopped" state (rather "waiting for a subsystem to start"). Similarly, if Internet Mail is stopped, you cannot start it just by starting the "avast! Mail Scanner" service.