jbard: If you have the exact same issue with a different ISP surely it must be a fault on your side?
I had the same issue with Orcon in Auckland 4 years ago... but Orcon uses Telecom infrastructure, doesn't it?
Since I have changed machines, browsers, operating systems, routers, and the problem seems to persist when I moved from Auckland to Christchurch... it looks like it can only be a program on my PC that I had used in all cases... maybe Google toolbar? SiteUp (a website monitoring software made here in NZ)? KeyText? Roboform? - These are the only programs I have used back then and still now, and which are constantly running... and all of them are rather above suspicion!
A clue: in both cases, the problem seems to have been triggered by browsing several pages of search results in Google images, and had not disappeared since.