Extract the PKCS#7 object:
$ openssl smime -verify -in file.msg -noverify -pk7out > file.pk7
Dump the certificates in that file
openssl pkcs7 -print_certs -in file.pk7 > file.pem
Open the file in your favorite text editor and seperate out each certificate individually in to it's own file and import:
For each CA certificate that you want to trust:
smime_keys add_root file.pem
Note: You do not need to trust all intermediate CAs. You can simply trust the end-user certificate.
For the subject certificate that you want to add:
smime_keys add_cert file.pem
If you have root access to the server, the easy way to solve such problems is to run sshd in debug mode, by issuing something like /usr/sbin/sshd -d -p 2222 on the server (full path to sshd executable required, which sshd can help) and then connecting from the client with ssh -p 2222 user@host
To prevent irrelevant keys from being offered, you have to explicitly specify this in every host entry in the ~/.ssh/config (on the client machine) file by adding IdentitiesOnly like so:
Host www.somehost.com
IdentityFile ~/.ssh/key_for_somehost_rsa