Hey, this sounds like the problem I had when I came back to the game about 2 years ago. It was stuttering terribly, at the same pace, constantly while in-game. Like you I tried everything I could think of but nothing stopped it.

Basically I got around it by moving my PC toward my router and used a direct ethernet cable instead of wireless, it sorted it out completely. Its very strange though because my laptop and 360 can both play FFXI wirelessly without the same problem, it was just my computers wireless that was throttling it for some reason.

Give it a try if you can.