Warning: DKIM: Invalid. reason='pubkey_unavailable'.

I've got 3 servers setup with DA and everything including DKIM exactly the same.

The only thing changed was the exim.conf to 4.5.5 update last night, because of the removal of 1 blacklist. And then the users on this one server could not send out messages anymore, they were refused as being spam.

Reason of spam: Waing: DKIM: Invalid. reason='pubkey_unavailable'.

So I removed all DKIM now for a quick fix. But how is this possible? All 3 servers have the 4.5.5 exim.conf an both others do not have this issue after updating the exim.conf last night.

What can be the reason this problem occured?