Hey Scarab, I'm sorry to hear you're having issues with this, and find it strange its happening across the board in your environment. I did a quick test in our public build test server and found no issues with domains already running DKIM, nor any issues in newly setup domains. Can you get a ticket submitted on this one so we can take a look?
Kyle Kerst
System/Network Administrator
SmarterTools Inc.
(877) 357-6278
www.smartertools.com