It is funny how the ONLY intelligent (and possible) solution to this issue would be most likely shunned by most of the playerbase.

Allow players to buy Gil legally, directly from SE.

Yes, it would be a "pay to win" system. Yes, people would hate it. Yes, RMT would disappear.

Other games implemented this quite successfully already, like EVE Online.