Availability on LGW-MLE is not as bad as people are making out, though not great either. But if you are prepared to book far in advance getting 2 seats in J is not unusual. I have been trying to get 4 and that is harder-to-impossible

We went to MLE in June this year but went via Asia. Basically did JFK-HKG-SIN on CX F for 135k each. Then we did SIN-MLE on SQ using US Air miles. Yes to do this in paid J costs about $2k each. But on US *A chart SIN and MLE are both "South-Central Asia" so return in J is only 30k miles each. Right now you can buy these miles directly from US for about 1.5cpm so you can basically buy two returns for about $900. Availability SIN-MLE was good at the time we booked it.

Probably not much help right now but once Air Berlin is integrated into OW they also fly to MLE from MUC.

Personally I really WISHED CX would do a non-stop from HKG. I have no doubt they could fill a 777 once or twice a week on this route.