You appear to have tried most things.
Try turning off IPv6.
Try using Safari's Reset control with most boxes ticked.
Try setting DNS server to 220.127.116.11 on your Mac.
Whilst changing DNS servers normally clears the DNS cache it is a good thing to flush the cache regularly - I flush mine once a day at boot.
If you still have problems post a few bad links here.