Maybe you can require this long process only for people that aren't in your country.
I don't know where you live, but here in Brazil having to get documents and signatures verified by a notary is super common (and super hated).
For example: I once wanted to unregister a domain I had. The only two ways of doing it were: don't pay the renewal fee OR get a paper form verified by a notary sent over snail mail to the registro.br office.
--------
Also, you may give your clients the option of verifying their signature at the embassy of the company's country in the client's country. This would skip on that whole Ministry of Foreign Affairs non sense.
--------------
A hacky way of avoiding this "excessive burden" problem is to offer all your users the possibility of linking their public gpg key to their account.
Almost no one would do it, but you gave them the opportunity to do so, thus you cover your ass at least a bit.
IIRC they also allow charging the person - for a "reasonable" amount - for the data retrieval process (which I assume would include the "identity verification" part).
Maybe using the 3-D Secure protocol (especially the second revision) would be enough to unburden yourself for verifying the identity as Mastercard/Visa/American Express supposedly check it for you.
This would work only in some conditions (the data subject should have a card to their name that supports 3-D Secure protocol, and you need to had a complete payment platform to your website/app/whatever) and doesn't solve all the other problems we have (like being sure we are delivering the right information esp. regarding homonyms and so on), but that could be something to investigate.
Just as a fun tidbit, I've grown accustomed to using Estonia's banklinks, and then like approx. 10 years after that the 3D-secure system starts appearing on foreign sites that almost provides the same functionality - it's nice to see finally some steps taken but damn, it's basically 20 years behind what everyone could have had.
The ability to charge is only for either (a) additional copies of data or (b) if the request is "manifestly unfounded or excessive." Given that there's no guidance on (b), that eliminates 99.9% of all SARs.
I live in dread of subject access requests (and thankfully have only had one, and it happened to be really easy to verify).