I would seriously give Australian Airlines a shot. They had announced that they plan to serve Kuala Lumpur (KUL) from their second hub in a Southern Australian city. Initially, they plan to fly into KUL on January 2003, but guess that had been heldback, given the situation in the South-East Asia region. There might be a slight chance that Qantas might actually return to KUL. The traffic between Malaysia and Australia is growing and there is definitely room for Qantas, or even BA to operate a KUL-Australia flights. The Malaysian government is also holding intensive talks with Lufthansa, BA and Qantas on the possibility of these 3 airlines to return to KUL.
I think SAS Scandinavian might be one of the carriers that are planning to fly into KUL as well. There are a lot of tourist traffic between Scandinavia and Malaysia. Currently, they have 3 weekly flights to Bangkok with a long layover time, which is sufficient for them to make a service to Kuala Lumpur. However, they could do a BKK-HKG run instead of a BKK-KUL though.
Egyptair was supposed to fly into KUL on August 2002, but they changed their plan later. They were supposed to fly CAI-KUL-SYD, but I guess the Malaysian government did not give fifth freedom rights to Egyptair. Plus, if I am not mistaken, Egyptair actually suspended their services to both Singapore and Sydney, so that might be another reason why Egyptair did not inaugurate services into KUL.
Air Macau recently inaugurated scheduled flights into KUL, flying twice weekly on Wednesdays and Sundays. Previously, they used to operate chartered flights into KUL.
SAA will probably not fly into KUL in the near future. If they do, I think it will probably operated as a code-share operations with MAS. They recently pulled out from Singapore and they only operate into Hong Kong and Bangkok now.
Xiamen Airways inaugurated services into KUL earlier this year with twice weekly flights to Fuzhou. ANA suspended its services in January 2002 and was expected to resume its flight operations in March 2003 when the summer schedules begins but they decided to suspend KUL in the end.