Virgin Media told me (after an hour on the phone going through the router reset charade) it's Netflix blocking the IP because it doesn't recognise the region (I think this is false, it worked fine before with this same IP). They said many other customers are having this issue and it would be resolved within a week. An arbitrary number given how we've had this issue for months now.
I then contacted Netflix who were going to call back with their "research team" and they have, a few days ago, spent 3 hours on the phone with me doing some WIreshark and other tests.
Turns out that Virgin Media is blocking secure connections on port 443 and this is why I can't use the service.
I have yet to contact VM about it, just don't have the time yet.