I had this same problem, a while back. First and most important question is: Are you using PC, and if so, are you using XP?
Microsoft released a service pack a few months ago (SP2) which, for some reason does pure hell to Final Fantasy connection. If you have automatic updates, it probably went into your system without you even realizing it. All I did to fix my problem was find where it sent my service packs (SP2) and deleted all of them.
No problems since.
(Microsoft has admitted that this problem <not just on FFXI> has been caused by the pack, its on their website)