Which provider are you talking about, exactly?
Exchange 2000/2003, or
Outlook/Exchange?
Outlook/Exchange protects Outlook (client program) only, and changes the status from "waiting for a subsystem to start" to "active" only when Outlook itself is running. Exchange 2000/2003 (and SMTP 2000/2003) is what you need on the server.