SQL Server 2008 :: Notify Operator Only Works Some Of The Time?

I've been working with Database Mail for some time but I haven't seen this one before. I have a maintenance plan that does the following:

1. Check database integrity
On Success:
2. Perform backups
On Success:
3. Perform a maintenance cleanup
On Success:
4. Notify operator of success

Steps 1 - 3 are also linked (via On Failure arrows) to a singular Notify Operator of Failure task.

The maintenance plan does exactly what I want it to, and if everything goes correctly, it successfully sends an email to an operator.

If steps 1 - 3 fail, the job ends in an error state, but does not trigger the Notify Operator of Failure task.

I was able to recreate the problem by creating another maintenance plan on the same instance with the same steps. Its "Notify Operator" on failure task also doesn't work.

It occurs to me that maybe I'm missing something, so here's some of the details of my SQL server:

SQL 2008 + SP1 (10.0.2531) x64 on Windows 2008 R2
DB Mail profile is public and default

I do have a slightly unusual profile, in that it uses two accounts:

1. A connection to a SharePoint SMTP service (where it catches emails directed at document libraries)

2. A connection to a UNIX-based smtp server (which routes mail to regular mailboxes and my SQL DBA mailing list)

The Profile will attempt to send to the SharePoint server first. The SharePoint server does not relay. If the document library email address doesn't exist, SQL will raise a warning (in the Database Mail log) and the profile will use the second account on the list, which is a real mail server and can relay the message to any mailbox.

It works really well, actually. When the maintenance plan completes successfully, the message is sent to the drop folder on the SharePoint server, and SharePoint routes the email to the correct library, and we have a central archive of all DB Mail notifications.

But if the job fails (for example, if the backup disk is out of space), none of this happens. According to the log, the job doesn't even try to send a notification. Looking at the DBMail log, the Mail service does not start. No email is delivered to the drop folder of the receiving SMTP server. So I don't think my Database Mail configuration is the problem here. It is apparently something to do with the way the job itself handles errors.