I hope my question isn't totaly off topic, so I try to ask.

I use several certificates with quite unusual subject/alt names. They are used for services like IMAP, SMTP submission, FTP access and other services. All services are public, but are accessible only for authenticated users. Each client has his unique hostname for every service and that hostname needs to be part of a certificate. So there is one certificate on every service (one for IMAP, one for FTP, etc.) and that certificate is valid for every hostname (which are uniqe for each user).

Hostnames are uniqe for the ability to migrate individual client's services between server nodes without the need to interact with the user.

This setup could be achieved by using simple wildcars (like *.imap.example.com), but in the past, when we started with this user/hostname/certificate approach, we used StartSSL certificates. They allow almost unlimited number of altnames in their certs, including wildcards - so we choosed to use something like *.*.example.com hostnames. The main reason was to prevent overfilling of our DNS zones with tens of thousands of records - so we nested the hostnames one level deeper:

12345.45.imap.example.com - user #12345
12346.46.imap.example.com - user #12346

And the certificate alt names looks like this:

*.01.imap.example.com, .., *.45.imap.example.com, ...

For long time we used this approache without any problems, until last year StartSSL was bought by Wosign and our certificates will become untrusted at some point this year.

I've already did some research if there is any other CA which would allow similar certificates but so far with no luck. Of course many of them would be happy to sign them for us - but for really, really high price (moreover, compared to free StartSSL certs we used so far).

Is there any way how to solve our case without spending a fortune for such certificates? Forcing our users to change their hostnames in mail clients and such is not an option.

It would be great if e.g. Let's Encrypt would support wildcards. Or is there any other "non comercial" CA out there that would be willing to sign such certificates?