А что другие почтовые сообщения с сервера приходят - в смысле SQL mail настроен и работает в других задачах ?
А через кнопку Test для Operator-a из Managament-SQL Server Agent-Operators тоже ничего не приходит ?

Но судя по этому сообщению об ошибке,
- либо у вас все-таки не настроен SQL mail (в Managament-SQL Server Agent-Properties в поле Mail profile в выпадающем списке должен быть почтовый профиль и кнопка Test должна выдавать что-то вроде "Mail session was started and stoped successfully")
- ваш SQL Server Agent стартует не под той учетной записью, которую вы используете для его настройки (могу предположить, что скорее всего с использованием System account, а не тем, под которым вы залогинилиь на сервере для запуска Enterprise Manager)
- либо и первое и второе.
Т.е. дело не job-e и не в том, как он использует notification, а все-таки в SQL mail.
Покопайтесь в данном форуме - вопрос настройки SQL mail уже несколько раз обсуждался, кроме того модераторы форума посвятили этой один из выпусков рассылки