Maybe you’ll find something at this type charity project.

Inspired by letterforms found on Sumatra — just slightly east of Indonesia:

http://www.myfonts.com/fonts/newfonts/nani/
http://www.myfonts.com/fonts/newfonts/tuktuk/

Usually, for things like this, lately people have tended to use typefaces like Ondine or even (shudder) Papyrus.

So, when it comes to the dull boring choices that have been overused, some other choices are

Slogan
Neuland
Legend
Mistral

For an authentic choice, though, some Googling located Padma, by Masuraj Sudana.

http://www.behance.net/gallery/Padma-Typeface/798617

is another link.

For Indonesia, there's FTF Indonesiana Serif Sketch by Fizzetica Type Foundry, and Tanah Air Beta.

If you really want to go the route of using a Latin script typeface to evoke a non-Latin culture, then my vote would certainly be for Padma. Note, however, that none of the types suggested in this thread are appropriate for continuous text, so you's want to limit something like Padma to headlines and other display use, and select a Latin text face that harmonises well with it.

Anything that gives a display face a certain mood can be applied in a text face too, just much more subtly. Looking at Padma (which I also like) I was immediately reminded of Papassissa's "Dr Jekyll & Miss Hyde":
http://www.typefacedesign.org/resources/A5specimen/2012/ElenaPapassissa_...
http://www.typefacedesign.org/2012/

hhp

I think Ben's Lumen from the same site would fit the bill nicely, if it was available to license.