I live in dread of subject access requests (and thankfully have only had one, and it happened to be really easy to verify).
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.
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.