Hi,
This problem has been solved at long last thanks to Lesley.
I split Malaysia's states across two zones: West Malaysia and East Malaysia. Then, I assigned different shipping rates to each of these zones.
Apparently, you cannot do this as it produces erratic results. I solved this problem by keeping all states within the same zone and using the Localised Shipping Module by Presto-Changeo.
I hope this helps somebody else.
Regards,
Luke