The rejection message you are getting is not from your exchange server, so either your MX records are pointing to the wrong IP or there is sometign else in between your internet connection and your exchange server.
It is also unusual to have a spam filter sending outgoing mail - it is more usually setup before receiving mail. Are you sure you have this setup correctly?
It may be that you have your mail arriving to your spam filter first and have not configured this properly.