Check your ALRT logs for SubmitMessage errors for this particular customer. The code associated with the error should help pinpoint the cause.

When the user composes a message, what does the "Send Using" line say at the top of the screen? Expected values would be along the lines of Default, Desktop, or a BIS-enabled e-mail address...