Windows Mobile program installation failure - “Installation was unsuccessful. The program cannot be installed because it is not digitally signed with a trusted certificate.”

There are scenarios where Windows Mobile phones have security locked down to require installation/setup programs to have a valid certificate from a trusted source.

Installation fails if the package:

#1. Does not have a certificate.
#2. The certificate included is self-signed/from an internal certificate authority (CA) and the phone does not have the CA in the Trusted Root Authority.

Solution, in order of preference:

#1. If the package has a self-signed/internal CA certificate, import the CA into the Trusted Root Authority on the phone.
#2. Remove the certificate requirement: Set HKLM\Security\Policies\Policies\0000101a to 1 using a Windows Mobile registry editor. Setting the value to 0 will re-enable the requirement.

Read more about the issue here and why, most of the time, having this security setting turned on is a good thing.