A big possibility is the ISP. I had a look at some reviews, here's one,
http://www.ciao.co.uk/Toucan__Review_5537877 and it aint too glowing. A while ago my emails were blocked to a friend overseas, turns out my ISP address appears to have been blocked by the company his ISP uses, because of spamming. (The only spamming I've ever done relates to food).He's having problems getting it unblocked. I wouldn't be surprised if this is a similar sort of case, in which case reinstalling windows or whatever won't make a scrap of difference. If you were going to change ISP's anyway, wait and see if that makes a difference first.