My comment regarding revocation was to clarify that unless you're currently revoking each of these certificates after removing a subdomain, there's probably no reason why you should remove the subdomain right away (instead of with the next renewal). I'm not suggesting you should revoke the certificates if this is just an implementation detail and not about actively revoking trust.

You're right that the default tooling would not work quite the way I described, but this use-case seems to call for a more low-level ACME library anyway, and with that it should not be too complex to implement some kind of bucket system where you just split your subdomains in buckets of 100 each, and occasionally rebalance them as subdomains are removed (i.e. merge two buckets into one when they have less than 100 subdomains total, etc.)