Microsoft webpages and Live Messebger don't work

Edit: Problem solved. Only affects customers of a particular Adelaide ISP.

I have not been able to sign in with Windows Live Messenger, or even connect to these websites (with either Firefox or IE):
http://www.microsoft.com/
http://messenger.msn.com/Status.aspx
http://home.live.com/default.aspx?mkt=en-au&lc=3081
http://support.microsoft.com/

The problem started last night. Other sites work fine: it just seems to be the one's to do with Microsoft that don't work.

The Windows Live Messenger Connection Troubleshooter says Key Ports is the issue (it gives green ticks to the other ones)

I have done a full scan with NOD32 and it found nothing.