Is there some sort of pattern to "certain addresses"? That would indicate a routing problem, perhaps external to the machine itself. Do other things besides telnet work? What about ping, traceroute, ssh?

Are you using DHCP? Did the machine's IP address change, like, for instance, not so coincidentally around the time the problems started?

Do you have working reverse DNS, and do the other machines possibly care whether or not you do? Is there anything else on their end which might be preventing the connections?