If you are experiencing trouble sending mail through Exchange and you check your Queue Viewer you may discover it's filling up with messages and the following error:

451.4.4.0 Primary target IP address responded with: “454.4.7.0 Temporary authentication failure.”  Attempted failover to alternate host, but that did not succeed.  Either there are no alternate hosts or deliver failed to all alternate hosts.

In brief, there is a problem with the connection between your Exchange server and your Edge transport server.  Next step is to check your Edge server for errors.  My particular issue involved an invalid certificate that, once resolved, cleared up this issue too.