This could be caused by a number of things.
The most likely include DNS issues, firewall issues and IP reputation problems.
I the mail is not genuine, then you could be an open relay or someone is authenticating to send spam through your server, so if it is not genuine, let me know. You will need to get this resolved before fixing the problem
If the mail is all genuine, and not SPAM, can you check using
http://testexchangeconnectivty.com - outbound connection.
Also might want to check the blacklists on
www.mxtoolbox.com Also check that port 25 is open from the Edge server to outbound.
Shaun