What Internet provider are you all with? I only ask because this sounds very similar to the the thread where people are getting lag with their ISP routing them to the FFXIV game servers through Level 3 (Comcast does this I think?).

Might be worth doing a traceroute to see if you go through level3.net, Behemoth's IP is apparently 199.91.189.40 (good test for any NA server as they're all in the same place).