Apple's primary technical support issue is people who are locked out of their Apple ID/iCloud/iTunes/etc. accounts for various reasons. It's tricky because another big issue is scammers trying to steal or break into other people's accounts.

It's also why Apple veers away from privacy by encouraging key escrow for iCloud - otherwise users will lock themselves out with no recourse.

In this case it sounds like it is Apple's fault and they should be able to fix it.

If you still own an Apple device (presumably you do if you care about the App Store) usually it can be registered (Apple may have to do this if you can't) and used for 2FA.

Since you own the payment method for your purchases, that should help as well.