lissie:sbiddle: The issue could be well beyond Telecom's network however, which isn't their fault.
What happens when you do a traceroute to the website? This should show where the routing issues lies.
tracert fails somewhere in the US - but my point stands - if it was the host's fault 2degreemobile wouldn't have connected me to the site
No thats not correct. Both Telecom and 2degrees have different upstream/peering arrangements and neither is in control about the network connectivity between their edge and the end site. TBH the people to blame here are Wellington airport for not hosting their site in NZ where there are virtually 1 to 1 connectivity between most major ISPs so these problems are sorted out very quickly.