Recipients Auto Rejecting Emails Sent With Exchange 2010 – Certificate Error

A strange problem recently developed with one of my Exchange 2010 servers. I have an exchange server setup as part of a Windows Small Business Server 2011 installation. The email for the domain was working perfectly for 4 or 5 months, and now with no change in configuration is having problems.

The inbound email still works great, but when an email is sent it occasionally bounces back with one of several error messages. It doesn't happen to all of the sent emails, just some of them. It appears as though mail sent to certain domains will always bounce, including mail sent to domains that used to work. It also seems like the error message is generated by the recipients receiving server. Here are some of the error messages that bounce back:

host123.SomeEmailHost.com rejected your message to the following e-mail
addresses: Someone LastName (aperson@adomain.com)

host123.SomeEmailHost.com gave this error: Verification failed for
The mail server could not deliver mail to
sender@sendingdomain.net. The account or domain may not exist, they may be
blacklisted, or missing the proper dns entries. Sender verify failed

A problem occurred during the delivery of this message to this e-mail
address. Try sending this message again. If the problem continues,
please contact your helpdesk.

Here is another message received when sending to a different domain:

mail12.anotherhost.com rejected your message to the following e-mail
addresses: someoneelse lastname (someoneelse@anotherdomain.com)

(someoneelse@anotherdomain.com) mail12.anotherhost.com gave this error:
sorry, that address is not in my list of allowed recipients; no valid
cert for gatewaying (#5.7.1)

A problem occurred during the delivery
of this message to this e-mail address. Try sending this message
again. If the problem continues, please contact your helpdesk.

I have tried researching these errors, but have not turned up anything that seems applicable to my server. Is it some sort of certificate error. I am using a self signed certificate on the server. If that is the problem, why did it just now start being a problem?

Any insight would be greatly appreciated.