The only shocking thing to me is this is the first time I’ve seen any story about this hole in the GDPR. This was one of the top reasons we blocked and deleted all EU users. How do I verify that a request is legitimately from a user, short of them arriving in person and providing some biometrics, which presumably we would need to collect from them in the beginning?

I have no idea. Any system with a high false negative rate is breaking the law, and one with a high false positive rate seems even worse.