The only Malay-ish restaurant I’ve been to recently is PappaRich, in one of the Xiniyi Mitsukoshi buildings. It’s alright, but I haven’t been in Malaysia or Indonesia for ages, so at this point I’m just happy to have a version, any version, of stuff that I recall once enjoying. Unlike other Indo-Malay places I’ve been to in Taipei, it’s also a nice restaurant, so you can sit with a drink for a while. It’s priced typically for department store restaurants.
There was a Malay place called White Coffee out Tianmu way. 台北市中山北路六段740號1樓. I haven’t been there in four years so no idea if it’s still there.
I vaguely recall hearing good things about Nyonya Kitchen (妞呀小廚), 台北市南京東路3段256巷20弄2號 - again, I don’t know if it’s still there.
There’s another place called Malaysian Gourmet Cuisine (馬來風光特色餐廳). I haven’t been there yet. I thought someone here recommended it, but search isn’t helping out with that.
Look around under Taipei Main Station. There are one or two Indonesian shops - there may also be restaurants.
I thought this had been brought up more recently, but apparently not. There’s this thread, last updated 2007:
And this one, last updated 2002!:
Oh, and this one, where I, um, kind of posted a lot of the same stuff actually:
http://tw.forumosa.com/t/recommendations-for-malaysian-or-singaporean-food/82434
And this thread over at Taiwanease:
https://taiwanease.com/en/forums/topic6388.html