The rejection document must be legalized by Taiwans representative office. It would be helpful if the rejection document clearly states why renunciation was rejected (which it usually does).
Then hand it it in your HHR. They will forward it to MOI. Then the exception to renunciation should apply, which is part of Taiwanese law.
If successful further can ask Australian embassy in Tawain to negotiate the renunciation exception to apply proactively, so renunciation rejection step would be waved in the future.
The problem in Germany it was not possible to legalize the rejection letter. So MOI in Taiwan decided (with a lot of diplomatic nudging) to skip renunciation requirement without asking for a rejection document. They might not do that for other countries where rejection document can be legalized.
This is true, but this is also prolonging the time and the number of hoops for myself. Getting the papers authenticated and recognized by Teco etc is very logistically demanding and I would have to do it multiple times. Plus I can reclaim anyway. So its not a straightforward better choice if it is lengthening and complicating the road.
Also, if a country makes the determination that it results in statelessness, they likely would not move from that position, as it may be unlawful to do so.