I think that updating your SPF records is going to be an important step in this case. HERE IS A LINK to an article from our resource center that outlines those steps. You'll want to get that to your IT team to implement on your email server.
You might also want to have them take a look at WHITELISTING.
Once these are in place, you'll want to move the error contacts back into active status and try sending to them again.