Interesting, I dont remember stamping when leaving Sabah/Sarawak for the mainland, only when entering.

Also remember got in a bit of trouble when I landed in Labuan and took a ferry over to Sabah. As the two are technically separate for immigration purposes if you do this route by plane you will go thru immigration at both LBU and BKI, but if you go by ferry, for some reason you don't. They asked me for a ferry ticket which I did not have. Had to spend like 20 minutes and was let go with a stiff warning.