As it doesn't work with OWA either it would exclude Outlook, Windows and the
user's profile as the cause of it. The issue would lie on the Exchange
server. Some quick checks;
-verify that there is no restriction set on the mailbox of the user (like a
send quota restriction and the conditions for that restriction is met with
the size of the mailbox)
-verify the logs on the Exchange server and that no general issues are
reported with the Exchange database or specific errors for that mailbox
-verify that the user (group) is allowed to send via the Send Connector
Either way, as the issue lies with Exchange, it's better to continue this in
an Exchange newsgroup.