What about batching requests into a queue? Or does it need to be synchronous.
If IPv6 is causing problems, can you disable it? Though a past ISP for me only allowed IPv6, so I can understand that being limiting.
Maybe a the cheapest possible VPS with fixed IP could act as a proxy (or maybe would have the same problem).
At from my side sounds like a fun problem to solve :)