Are you running the latest public release in this environment, Richard? We had a known issue in the past involving DKIM private keys becoming corrupted or missing in some cases, and I believe this error could be generated in those scenarios. If you take a copy of the domain's settings.json file and open it up, do you see a private key under dkim_private_key? (Don't post that here! :))
Kyle Kerst
System/Network Administrator
SmarterTools Inc.
(877) 357-6278
www.smartertools.com