Suggestion:
Is it possible that you can integrate a verification feature into your service that would call the customer, request them to leave a message with their name and email address and then make sure that the phone number's location is in the same state as the PayPal billing address. Currently, I do this tediously with Google's GrandCentral (www.grandcentral.com). After the customer submits the message, GrandCentral displays the city and state
and I match it up with their PayPal verified address. Once I do that, I send them a pre-formated email with the game card code. I realize this would slightly stray from your regular business model but maybe you can at least find a way to integrate your service with a service at least similar to GrandCentral. (By the way, GrandCentral is free.)