Certificates signed by multiple CAs

Solution 1:

No, it's not possible for an X.509 certificate (the type used by OpenSSL) to have more than one signature. However, you can issue multiple certificates that will do the same job.

Provided you keep the key and subject the same, you can create multiple CA certificates that will each satisfy as a valid issuer certificate for the certificates that (those?) CA(s) issue. These CA certificates may themselves be self-signed, or issued by different CA as what's called a cross-signed certificate.

The other answerers are correct: any commercial CA will want to very thoroughly examine your policies and procedures before cross-signing your CA. That said, it's definitely possible from a technical standpoint.

If the users you're talking about are using only devices you control (i.e. they're internal users), then I suggest installing your root CA certificate on those devices. This is what many large companies do (and I actually do it on my own network!) and allows you to issue internal-use-only certificates as much as you like, in accordance with your own policies.

If, on the other hand, the users are external to your organisation (or even employees working from home, for example) then it's probably best to have certificates issued from a trusted, commercial CA. If you'll be needing a lot of these certificates (5+ per year), most commercial CAs have programs that ease the administrative burden and often decrease cost; if you'll be needing a truly large quantity (I'd not even bother looking unless it's more than 100 per year), you can consider approaching a CA to setup a custom subordinate CA (but as above, they'll likely want you to setup a new CA according to their policies rather than cross-sign your existing one).

Solution 2:

It would be nice if we could get those certificates signed by another CA to increase trust.

Even if this was possible it wouldn't increase the level of trust, because an untrusted party also signed the certificate, which means the certificate in general should not be trusted. I suggest you just sign everything from a new CA vendor that the major platforms actually trust.