I sent from Bali to Perth by air in February -08... but because of aircraft loading door size, the bike had to fly via Melbourne! It was done with Quantas, there was also Garuda Indonesia flying that route, but they claimed their limit per package is only 50kg. I got the feeling they just didn't want anything to do with the whole thing. My freight agent in Bali was CAS Cargo, they're specialised in sending furniture, art and so on, mine was the first bike they'd sent, and it showed. For example, they had the wrong Dangerous goods codes in use, and I told them that when I saw the paper. They still insisted it's correct ,but at the airport it turned out it wasn't, and we had to rush back to their office to redo the papers. In the end the shipping went ok, no problems at all when arriving to Oz (but remember, the bike MUST be 'clean as new', or you get lotsa trouble!)

Not sure if I could recommend CAS Cargo.. But I can check, if I still have some contact info, if you want to ask them.

BTW, as others already pointed out, you have a bigger problem getting the bike from Malaysia to Sumatra, than it might appear on the map. Back in -08, there was the commonly used onion boat route with Cakra Shipping from Penang, but I hear they now help only, when going Indo->Malaysia. There probably will be a way to do it, when you get there. But to know about that solution right now is practically impossible, because the only constant thing around there is change.

Also it is good to keep in mind, that Indonesian customs can become a real show-stopper, so it would be good to be able to use the 'more commonly' used points of entry. That would probably still be Belawan in Sumatra - but will there be transport to go there, I don't know.