I have an email into the HMRC to clarify how to deal with location issues related to place of supply for web-based businesses. I have not heard anything back yet in 24 hours.
I also reached out to Braintree Payments, who I am planning on switching over to. They linked me to documentation showing that credit card payments provide a bunch of bank info including “transaction.credit_card_details.country_of_issuance”. https://developers.braintreepayments.com/javascript+ruby/reference/objects/transaction#transaction.credit-card-details.masked-number
Unfortunately I’m only seeing billing country for PayPal payments once the payment is complete. It seems you can set tax rates within PayPal for specific countries, but this doesn’t really help with confirming two pieces of evidence.