¿Tu servidor tiene Outlook instalado Y configurado? Es necesario para que sendmail funcione porque depende de MAPI (unas librerías de M$ para correo).
Si ya lo tienes entonces entra en la configuración del servidor (y del SQL Agent) y selecciona el perfil de mail que configuraste en el Outlook, para ligar la cuenta con el servicio de SQL Server.
Una vez hecho esto prueba de nuevo...
Algunas veces es necesario llamar a xp_startmail de manera explícita, aunque
en teoría el propio xp_sendmail lo debería hacer.
Si todo falla siempre tienes al SMTP que funciona mucho mejor:
http://sqldev.net/xp/xpsmtp.htm
Suerte