Sorry if this seems like a "did you check the power cord" answer, but you mention that you have two certificates. Are you positive that the one you are encrypting to is the one which is installed in Outlook?
-- Mike Schiraldi VeriSign Applied Research
msg24705/pgp00000.pgp
Description: PGP signature
