The digital ID cannot be found by the underlying security system - with signed-only mail

In preparation for encrypted email traffic, someone@elsewhere sent me a signed (not encrypted) message.
In Outlook 2007, the message cannot be opened with error see above. (Signed messages from other senders are ok)
In Outlook web access, the message opens fine (with a suitable warning)
In Outlook 2010, the message opens fine and allows viewing and exporting the senders certificate.
In Outlook 2007, I created a contact for the sender someone@elsewhere and imported that certificate - still the error.
I even tried to import (via IE) the root CA and intermediate certificate - no change to the main problem, though the conatct certificate now show as trustworthy even without explicitly trusting it.

What can be wrong, what can be done?
(It should not make a difference, but the sender uses Mac or so)

The following old threads did not prove helpful:
https://www.experts-exchange.com/questions/24773972/Can't-open-this-item-your-digital-ID-name-cannot-be-found-CANNOT-BE-FOUND-BY-THE-UNDERLYING-SECURITY-SYSTEM.html
https://www.experts-exchange.com/questions/23915360/Exchange-Certificate-Issue-Digital-ID-name-cannot-be-found-by-underlying-security.html
https://www.experts-exchange.com/questions/22010029/Can't-open-this-item-Your-Digital-ID-name-can-not-be-found-by-the-underlying-security-system.html