Problem is, there's a little of 4 billion ipv4 ips and getting one someone else has used before wouldn't be impossible. Your provider may only sold that ip in there logs once and it was to you. But issue is that proxy could of been used by others. Another issue could be where the provider is getting them, or how high quality they're, etc. If you get anymore proxies from them and they cause locks like this, I would plain out say they're just shit proxies, and you should switch providers.