Hi Peter,
I think one of the most interesting part of our hobby is the research, you can really find out interesting bits of history if you take a chance.
I tried Google too and found only the few data you already have on Kinabalu. The search for the company proved no more successful, but found a company named "Yayasan Sabah Shipping", the street address is 88817 Kota Kinabalu, Sabah, the fax number 608-8426755 (I don´t know if the country code is included). It´s a veeery long shot, but maybe it´s worth risking a fax, you never know.
Enjoy your research!