Hi guys,
With help from everyone in this thread, the problem has been resolved. I'll try to wrap up the steps so hopefully if someone searches for the thread they can get a lot of info. This has certainly been an informative lesson for me. Thank you everyone for all of the input!
Symptoms:
Client sends an email from an alternate account stating that they "could receive but not send any emails." I ask if there are any bounce backs or errors, they forward me a bounce back with details of their domain being blocked by Spamhaus.
Resolutions steps:
1) Go to Spamhaus.org and request to be delisted from the blacklist. This may not have been the proper first step. In my situation, I had literally just changed the location of the exchange datastore so I was under the impression that somehow this had caused the blacklisting and not true Spam. Within about 6 hours, the domain was back on the blacklist.
2) Client had an existing Sonicwall, so I logged in and blocked all traffic LAN->WAN for port 25. I then created an exception for their exchange server IP so it was the only server allowed to send out email.
3) Enable logging on the port 25 block, and start reporting in the Sonicwall software.
4) Ensure that the Exchange Server cannot be used as a relay. Check the exchange logs for excessive emails, just incase. Email looks normal, regular traffic from the usual email addresses. Server looks clean.
5) Run anti-virus scan on the server. Ask client employees to run anti-virus and malwarebytes on their systems (believe me, only 1/3 of them or less will actually do this)
5) Check the firewall logs for hits against the block. Check revealed a ton of dropped attempts from a single IP against port 25.
6) Run a quick IP scan software from the server to get the computer name of that LAN IP.
7) Take workstation off the network and clean it up! Plug it back in.
8) Verify that there are no new hits against port 25 on firewall.
9) Delist from blacklists. Use mxtools.com to check multiple blacklists at once.
10) Recommend edge based spam filtering, spam filtering service, or in this case switch the client to O365 because it's a great fit!
