I've just had a look at this having come across the same issue as you.

The outbound path seems fine, and isn't really relevant given the direction of traffic. The return path is more important given this is download traffic and this is likely to be out of Vodafone control, the return path is from the perspective of the usenet provider doing a traceroute back to your home IP.

Most of the usenet providers are advertising their addresses out of the same AS34305 - they peer with highwinds network group (stackpath) which is AS12989 and AS33438. Paths back to Vodafone NZ from those AS in a looking glass doesn't look very clean. Looks like a change in highwinds networks that's probably caused this, so as Voda mentioned once it leaves their network the internet is the wild west and just because your traceroute out looked like it did, often the return path is completely different.

On the outbound path the international leg was core2site which are pretty good (vodafone peering), but the return path is completely different (Up to the other ends ISP) - the international return used some different path back to NZ using CW-CWINTERN-NET - this might be where to look.

Anyway, after that super quick look perhaps I'll need to change ISP as well - but won't be blaming Voda while doing it.