If you didn't run EA DomainKeys/DKIM installer under Domain Administrator security context, the DKIM agent won't be installed correctly.
You can verify the installation like this:

Exchange Management Shell->

Get-TransportAgent

There is no "EA DomainKey Agent" installed, then you can fix it like this way:

Exchange Management Shell->

Install-TransportAgent
Assembly Path: c:\Program Files (x86)\EAExchDomainKeys\EAExchDomainKeys2007.dll
Name: EA DomainKeys Agent
TransportAgentFactory: EAExchDomainKeys2007.DKSignerFactory

Enable-TransportAgent
Name: EA DomainKeys Agent

Then restart MS Transport Service, it is ok.

If your OS is 32bit system, please change "c:\Program Files (x86)" to "c:\Program Files"