Blacksheep, thx for correction on spelling of hotel name. Think I had a few too many last time I was there and got a bit muddled on spelling!!!
Greycone, If you're with the other half I have to recommend Mulu. There is a resort called Royal Mulu Resort (spelling correct this time). You have to fly there. You can visit caves which are quite spectacular. You only need about two days to see all worth seeing. You could catch full fare MAS flights for about IEP50 each...maybe less from KK. May have to transit at Miri. There are no roads cos it's in the middle of the jungle....but you can catch a boat from Miri or Limbang. I believe the boat trip is good...but about 4 hours!!!
FYI rates at Royal Mulu are 140 Malaysian rinngit nett inc b/fast. Tanjong Aru a little dearer. Airline ID reqd for those rates.
Lots to do around borneo really. If you need more info just let me know.......Slainte
PS Blacksheep...are you in the same place as me????