чтобы пользователь мог послать сообщение необходимо присвоить ему права Execute не только на продцедуру из которой идет посылка сообщения, но и на xp_cmdshell ... что нехотелось бы делать из соображений безопасности

BOL - Transact-SQL Reference - SET - System Stored Procedures - xp_sqlagent_proxy_account
" SQL Server Agent proxy accounts allow SQL Server users who do not belong to the sysadmin fixed server role to execute xp_cmdshell and own SQL Server Agent jobs. The administrators can assign appropriate security permissions to the proxy account to control the ability of these jobs to access resources in the network.

When a SQL Server user executes a command prompt command using xp_cmdshell, the command must execute in the security context of a Windows account. If the SQL Server user is a member of the sysadmin fixed server role, SQL Server executes the command prompt command using the Windows account under which the SQL Server service is running. If the SQL Server user executing xp_cmdshell is not a member of the sysadmin fixed server role, SQL Server executes the command using the Windows account specified as the SQL Server Agent proxy account . If no SQL Server Agent proxy account has been set, the user gets an error.

Syntax
xp_sqlagent_proxy_account
{ N'GET' |
N'SET', N'agent_domain_name', N'agent_username', N'agent_password'
}
"
NB!
- При использовании xp_sqlagent_proxy_account проверка заданной учетной записи не производиться
- Все параметры чувствительны к регистру

Эту же операцию можно проделать в EM - Managament - SQL Server Agent - Properties - Job System - секция Non-SysAdmin job step proxy account

Если вы хотите, чтобы пользователь сам запускал xp_cmdshell, то конечно ему нужны соответсвующие права.
Либо можно создать свою процедуру(с владельцем dbo), которая будет запускать xp_cmdshell с уже нужными параметрами и только с ними и разрешить пользователю запускать эту процедуру. Тогда явные права на xp_cmdshell пользователю не нужны.

Но и в том и другом случае права для запущенной через xp_cmdshell программы будут определяться SQLServerAgentproxyaccount - ом (если пользователь не sysadmin)

1.
При выполнении пользователями sp содержащих net_send_message ошибки не происходит но и сообщения не посылаються
Что возвращает xp_cmdshell ?

2. У SQLAgentcmdexec имеются достоточные права внешнуюю программу ?

3. Попробуйте использовать какую-нибудь другую локальную или доменную учетную запись. В качестве эксперимента можго попробовать и учетную запись локального администратора