It's normal for the OUTLOOK/EXCHANGE provider to be waiting because I dont have OUTLOOK installed, but the WEB SHIELD and INTERNET MAIL providers have always worked in the past (with dial-up).
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.
But, coming back to your case, check the avast! services?
Start > Control Panel > Administrative Tools > Services
I suppose you have to have four avast! services:
C:\Program Files\Alwil Software\Avast4\ashServ.exe (avast! antivirus service)
C:\Program Files\Alwil Software\Avast4\aswUpdSv.exe (avast! Update Service)
C:\Program Files\Alwil Software\Avast4\ashWebSv.exe (avast! Web Scanner service)
C:\Program Files\Alwil Software\Avast4\ashMaiSv.exe (avast! e-Mail Scanner service)
The two first of them should be Automatic loaded and the two last Manually loaded.
Also, into the firewall settings, the following programs should be allowed to connect:
C:\Program Files\Alwil Software\Avast4\ashWebSv.exe (avast! Web Scanner)
C:\Program Files\Alwil Software\Avast4\ashMaiSv.exe (avast! e-Mail Scanner Service)
C:\Program Files\Alwil Software\Avast4\Setup\avast.setup (avast! Update executable). This is a temporary file that just appears when an update (check) is about to launch, and disappears again afterwards.
Don't need rights to connect:
C:\Program Files\Alwil Software\Avast4\ashServ.exe (avast! antivirus service)
C:\Program Files\Alwil Software\Avast4\aswUpdSv.exe (avast! Update Service)