Marc,
I am having the exact same problem. I saw this on the Apple
Discussion threads:
http://discussions.apple.com/thread.jspa?messageID=6512267
But that was it and I was not willing to nuke my keychain. I did nuke
the certs for the server with the problem but that did not help.
It is interesting to note that I only get this in Apple Mail with one
of my accounts. I have 5 accounts on several different servers and
digitally signing messages works on those other accounts. It is just
this one.
Jonathan