In checking further into this issue it seems there is a HUGE range of IPs that are blacklisted by Symantec and we happen to fall into that range.
It seems every one of our public IP addresses is blacklisted with Symantec for "Snow shoe spamming".
I checked all our neighboring public IP addresses, well outside our own subnet, and they are also blacklisted. It seems Symantec has decided to blacklist a huge range of IP Addresses and we happen to be in the middle of it.
I checked 250 some other blacklists using this tool: http://multirbl.valli.org/lookup
and all of the IP addresses I have checked with this are showing as clean for every other blacklist out there. It is *only* Symantec that is blacklisting this range of IP Addresses and causing us major problems emailing to some clients.
Our IP addresses affected are 173.239.120.225 through 173.239.120.254.
I have checked IP Addresses 173.239.115.1 through 173.239.121.254 and ALL of them are blacklisted with Symantec, but show as clean on every other blacklist on the internet I can check.
At this point I don't know the full extent of the range of IPs affected but it is quite large. So the issue is definitely not with us individually, but with Symantec deciding to blacklist a massive range of IP addresses for an unknown reason and apparently leaving us no way to investigate or resolve this!
Please let me know what you find with this, and if you're able to be of assistance!