I'm banging my head against the wall here.
I know this is a very vague question and it could quite possibly be a multitude of issues, but I'll try my luck anyway.
We have an email server running an old version of IMail.
On Wednesday of last week the server went down and we quickly threw it on another machine to make it operational for the time being. In doing so, we changed the outside IP address of the mail server.
Everything worked fine for a few days, or so we thought.
I came into work Monday morning and email was very sporadic, a few emails would get through, but most would not.
Come to find out that the spool folder was completely full and email was simply not being processed. In the course of fixing that issue, my boss wanted me to briefly turn on Open Relay on the mail server. Don't ask why, I question his decisions often.

I quickly realized it was causing us to take an enormous hit and turned it off.
Mail is working fine now, expect for the fact that we are being blocked by some domains that we were previously able to send to. Would this be due to briefly setting the server to open relay, or the outside IP change?
It's causing me a lot of headaches. I am not at all familiar with IMail and only know the basics of email server operation, so I'm having trouble figuring out what is going on.
I do not have contact information for people in these domains, let alone someone who can actually get into their mail servers.
Suggestions?
I have logs and any other information that you may need to help me!