Una solución temporal es que fuerces el cambio de ip (desde cmd o en ajustes del router), y con suerte se te asigna una sin ese problema. Puede que necesites tener el router apagado 5 min para conseguirlo.
Es temporal porque a poco que se te vuelva a cambiar y se te asigne una IP ukraniana o no española, te va pasar lo mismo, así que está bien que hayas contactado con la compañía. A parte de que son ellos los que tienen que solucionarte la papeleta, si reciben mas quejas de ese tipo se preocuparán mas para que sus pool ip sean de mas calidad y evitar este tipo de problemas.
Hace un tiempo me pasó algo similar, la ip era española pero bloqueada por muchos sitios incluso google, tenía que rellenar recaptcha a casa paso que daba, a saber que habían hecho con esa ip anteriormente... me lo solucionó la compañía, según me comentaron algo de cgnat.