Does Malaysia have an outbound immigration check at the causeway bridge linking it to Singapore? If not, wouldn't just driving to/from SIN and flying through there eliminate many of the issues of whose passport you entered/exited with?

It might be inconvenient and add expense, but using the bridge and flying within MY via Johor might make things easier if there is no outbound check at any of the bridges.