Trouble With SQL Mail Notifications

I am trying to set up event notifications via email (MS Exchange). Following the instructions here...
http://msdn2.microsoft.com/en-us/library/ms190724.aspx

I have an outlook profile created on my sql server for the same domain account which starts up SQLSERVERAGENT. I can send/recieve emails in this account, and running xp_sendmail in Query Analyzer works as expected.

However, when trying to set up an "operator" and testing the email ability, I get the error...
Error 22022: SQLServerAgent Error: The SQLServerAgent mail session is not running; check the mail profile and/or the SQLServerAgent service startup account in the SQLServerAgent Properties dialog.

I am running Outlook 2003 using Exchange. I seem to be having the same problem as this person.
http://www.experts-exchange.com/Databases/Microsoft_SQL_Server/Q_21627245.html

However, it makes reference to MSExchangeIS which I cannot find on my SQL Server. I would assume this to be a service of Exchange which would be on a seperate server entirely. If this is just some type of "connector" service that can be installed on any server, then how would I go about installing it? I presume that I need this service to get these mail notifications working, no?

This must be a very common situation since everyone needs to know when their jobs are working or not. Any help is greatly appreciated.