The simple solution to this is to promise that any browser instances outside the EU will label these certificates as invalid with very big red scary warnings (maybe mumbling something about risk of state-sponsored attacks). The CAs trying to push those certificates will then quickly lose interest in pushing this regulation...

Within the EU, this can also be solved: Pop up a dialog with the certificate, showing "This web site uses a special kind of certificate that <browsername> is by law required to accept. <issuing authority> from <country> claims that this web site has the following identity <claim>. Such certificates are typically used by (explain whatever the intended use case of these certificates is supposed to be). If you do not expect this web site to use such a special certificate, this may be a government-sponsored attack. The below text will help any technical people investigate. <base64 of the certificate> [ ] do not show again for this certificate and site".

That fulfills both the letter and the spirit of the law while making it very unlikely that these certificates can be used maliciously (and if they were, would make it extremely likely that signed evidence of that would quickly show up). Optionally, allow site operators of major sites to indicate that they will never use such certificates.