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.