You appear to be suffering from the certificate cancer that is spreading. The problem is that there are 2 certificates with the same name "DoD Root CA 2", one of which is the real Root CA 2 (expires in 2029), and the other (expires in 2011) is an intermediate cert signed by "DoD Interoperability Root CA 1". Having 2 important certs with the same common name was a REALLY BAD IDEA on someone's part. A number of applications appear to build their certificate chain based on just the common name rather than other attributes, and therefore will often choose the wrong one. I know that both Thunderbird and Entourage suffer from this.
For example, I can see that your email is signed, but uses the wrong DoD Root CA 2, and therefore you have the cancer...
If you have the wrong chain, then your signature cannot be validated.
If you delete all the bad certs out of keychain, things start working better. Unfortunately, the minute you open an email from someone that has the cancer, you will be re-infected and the bad certs will reappear in your keychain. Each time that happens, you need to delete them out of keychain again.
#!/bin/sh
echo Delete Certs from Login Keychain
security delete-certificate -Z EEA68FC8701E41E6429A341AE4162BBDA634F7F4 ~/Library/Keychains/login.keychain
security delete-certificate -Z 3BAE7B920EE6616755BE4FA287777EEF2F6B33F6 ~/Library/Keychains/login.keychain
security delete-certificate -Z DC92F91BAB283472023B32178504E19BF7D9A94C ~/Library/Keychains/login.keychain
security delete-certificate -Z 0A0E46657F4148DF2D1C6778EA9308A8CA41989F ~/Library/Keychains/login.keychain
security delete-certificate -Z 3EC3482D419C542EC1A3ADCA4DB8F9A23F787321 ~/Library/Keychains/login.keychain
security delete-certificate -Z CB44A097857C45FA187ED952086CB9841F2D51B5 ~/Library/Keychains/login.keychain
security delete-certificate -Z BDAA73F208F89E5481761033B1C008A8D253C776 ~/Library/Keychains/login.keychain
echo Done!
Crude but effective. Some put this in a cron job and just run it every 30 seconds.
Then, the other thing you need to do is find everyone that sends you mail that has the cancer, and get them to clean up their certificate store (different for every OS and mail app, unfortunately), so they don't continue to spread the cancer.
Once you do all this, we've found that things start working a lot better.
A better solution, of course, is to get the mail apps (T'bird, Entourage, others?) to pick the correct cert when building the certificate chain in signatures. Or, maybe someone on the list has a better solution.
--Ron