1. It's become clear this is not really working, since many banned players keep repeatedly being banned on new characters anyway; and,
2. Prohibiting VPNs is not good for users on many levels. Everyone should be using a VPN (especially so with such a hyper exposed protocol) and as the last data breach showed, there are some legitimate privacy concerns.
There is another option, and in fact the most common way that virtually all online services verify users and protect against bots and ban circumventions: SMS verification for account creation (or alternatively for membership).
This type of service is almost ideal from a privacy standpoint because many of them don't expose user data to anyone else, they just tell whoever is verifying whether the number is good and unique. This type of service also allows for doing things like two-factor authentication for high security tasks like changing passwords, although that requires more actual development to integrate.
From what I've seen this type of service usually costs something like ~5-10c per verification, and although it's not totally foolproof to circumvention, it's the method of choice for several big F2P games to control cheating and ban circumvention and bots. A small number of users would possibly have issues being on smaller pre-paid cell networks in certain countries, but I think having to allow only for a couple of exceptions a year would make it far easier than prohibiting important privacy mechanisms to everyone.
From what I saw some of these services are geared towards very small clients with minimal setup required, however there would be at least some setup to implement it. I do think this is something to at least consider, and might be a good use of some of the money that has been set aside for the game's development to be used on.