The easiest way to determine what is going on is to use the latest version (2014 R2) of Rebex Secure Mail and create a communication log. The latest version will actually log Windows CryptoAPI error code that caused certificate validation to fail (unlike the previous versions, where additional code was needed to determine the cause of the error).
In case your support contract expired, please try this with the trial version - once we know what caused the error, it might be possible to work around using one of the old releases as well.