No need to buy direct from EK ex-KUL. Although it has a best price guarantee, that is only valid for webfares. Last time I was in KL, there were plenty of non-web agents in town who would sell discounted fares - e.g. MYR6000-7000++ promo fare in C to Europe (with some flight/date restrictions). Sorry, I can't help you with names of agents though (...but there was one next to the famous beef ball noodle shop in Chinatown!)
Other potentially cheap alternatives are GF, BI (but is it dry?) and KL (direct to NCL, and MH codeshares to AMS also included in some fares)