TL;DR;
To change a contract from my wife to my name CHT (中華電信) wanted almost 3k deposit and a guarantor. I argued with them and won. No deposit and no guarantor.
The contract originated from that awesome deal CHT had a few years back.
Because it was insanely popular and a short promotion the CHT locations were swarmed with long lines. By the time we got our turn it was well past closing time and every worker was tired. Because of those circumstances, it was not possible to push the issue with deposits/guarantor and we got the contract in my wife’s name to avoid all of that.
That is not ideal as the identification verification using the phone number won’t work.
Yesterday my FIL wanted to change a contract, so we went to do that. I remembered the issue about my contract and wanted them to change it to my ID number. They said they need to change the whole contract to my name and that would require a deposit (ca. 3k) and a guarantor because I am a foreigner.
I knew what was up and started a show of how upset and offended I am. 
(Feel sorry for the girl at the counter as she did nothing to deserve that)
That prompted two managers to come to us to assist. I showed them the law about the non discrimination based on nationality, since Taiwanese are not required to pay that. Their interpretation is different of course, since they discriminate against all foreigners equally, that law does not apply.
They tried to persuade me to accept the deposit since I will get it back when I leave Taiwan! I told them I am permanent resident and not going to leave ever, so are they going to keep it until I die?!
I also threatened them with making complaints to authorities about such discrimination.
With this performance I was able to get all those requirements waved. No deposit and no guarantor.
But I am sure next foreigner who will walk in, will be asked for a deposit/guarantor again…
Helpful for my case were:
APRC
contract that was always paid in full on time over many years
(probably because I am a Caucasian Westerner)