It helps to get on the phone and ask in your best southern accented Mandarin. My experience is that the bureaucrats in Taipei have much more patience. Phone number of BOCA in Taipei is +886 2 2343 2840.
Edit: refer to section 16 for the relevant regulations https://www.boca.gov.tw/cp-211-429-86eaf-1.html
Him being able to trace his patriline to someone recognized by the ROC to be one of its nationals.
Neither being born in China or living in Taiwan entitles a non-stateless person to nationality. It has to be demonstrated through descent, patriline only for births prior to 1980.
Section 16 refers to Mainland Area Person that settled abroad. What would be the relevant regulation for the OP who ceases to be a Mainland Area Person?
Thank you for all your clarifications. Now all this is much more clear for me. I believe the key issue here is the lack of documentation issued by ROC authorities proving the identity of my parents and grandparents.
How about this
有關具外國籍之大陸地區人民，申請以外國人身分與國人在臺辦理結婚登記事宜
It is 94 年 1 月 28 日台內戶字第 09400762762 號函（諒達）辦理身分變更事宜.
有關大陸地區人民、香港澳門居民及台灣地區人民取得外國國籍之身分認定及身分變更登記相關事宜乙案
https://mlhr.miaoli.gov.tw/law.php?page=209
內政部函【說明二】有關旅居國外4年以上且取得外國國籍之大陸地區人民，准予其身分變更為外國人，嗣後並得准以外國人身分申請歸化我國國籍。
People who were nationals in Mainland area but got a foreign nationality and have lived abroad for more than 4 years can be foreigners, so they can get a ROC nationality by naturalization.
Isn’t it?
曾經在大陸地區的人士，如果持其他國家的護照申請來臺簽證，有什麼特別的規定？
https://www.boca.gov.tw/cp-78-683-859e0-1.html
依據「臺灣地區與大陸地區人民關係條例」暨其施行細則規定，大陸地區人民如果旅居國外4年以上，並且已經合法取得居住國的國籍，得持該外國護照申請來臺簽證。（僅限正式護照，持非護照之旅行文件如「旅行證」，則非我國簽證之核發對象）
It seems that we have 2 situations above:
A mainland citizen living abroad for more than 4 years and holding a foreign nationality can be considered a foreigner when applying for residency in Taiwan.
A mainland citizen living abroad for more than 4 years and holding a foreign nationality should use the foreign passport when applying for Taiwan visas.
Is this correct? Does this mean that from a ROC point of view those people lost their ROC nationality?
In both cases we are still talking about mainland citizens, I mean people who keep PRC nationality and hukou even after obtaining foreign nationalities (by the way, which is not allowed according to the PRC nationality law).
What about the overseas that are no longer PRC citizens?
First case:
內政部函【說明二】有關旅居國外4年以上且取得外國國籍之大陸地區人民，准予其身分變更為外國人，嗣後並得准以外國人身分申請歸化我國國籍。
“Explanation 2” in the MOI’s letter concerns a Mainland Area Person who sojourns abroad for 4 years or more and obtains a foreign country’s nationality, his/her identity changing to that of a foreigner, and afterwards may as a foreigner apply for naturalization to our country’s nationality.
It suggests – but doesn’t explicitly say – the person lost ROC nationality by naturalizing abroad. So I would say your way of putting it (“can be considered a foreigner”) is reasonable.
Second case:
依據「臺灣地區與大陸地區人民關係條例」暨其施行細則規定，大陸地區人民如果旅居國外4年以上，並且已經合法取得居住國的國籍，得持該外國護照申請來臺簽證。（僅限正式護照，持非護照之旅行文件如「旅行證」，則非我國簽證之核發對象）
I’ll just change one word in your summary.
A mainland citizen living abroad for more than 4 years and holding a foreign nationality should may use the foreign passport when applying for Taiwan visas.
And I’ll add the parenthetical sentence.
(This is limited to formal passports; the holder of a non-passport travel document such as a “travel pass”[?] is not the object of our country’s visa issuance.)
HK and Macao residents who hold foreign passports issued after the handover dates are not allowed to apply for the entry permit to visit Taiwan. They must apply for a visa for foreigners.
Can we conclude that those ROC nationals lost their ROC nationality?
The ROC allows persons with dual nationality to enter on foreign passports and treat that person as a foreigner for length of stay and visa purposes. A dual national is not prohibited from applying for an ARC (but is prohibited from applying for an APRC - to the surprise and consternation of quite a few ABTs who didn’t realize they were dual nationals until their application got rejected). That doesn’t mean the dual national ceases to be a ROC national.
Now question is if the ROC recognizes the act of a PRC national renouncing PRC nationality to a PRC consular officer as renouncing ROC nationality. I would think not…That could result this person falling outside the definition of Mainland Area Person (one of multiple categories of ROC nationals) but does not affect the underlying ROC nationality. I would think ROC nationality needs to be renounced to a ROC consular officer.
though, I think the 內政部函 saying those people can do naturalization as foreigners.
It seems like the gay marriage paradox: it’s simultaneously marriage and not marriage… or simultaneously loss of nationality and not loss of nationality. 
After the APRC is rejected which options do they have?
Stay on ARC, or if they want a permanent residency, they should get hukou. Or renounce their ROC nationality?
I am also very curious about this topic. I have emailed the Ministry of Interior today asking them about it. However, mine is not about whether a former PRC national has ROC nationality, but rather can a current PRC national obtain proof of ROC nationality via 中華民國國籍證明 (ROC Citizenship Certificate)
Basically here is my logic: (My sources are in Chinese, assuming that most ppl here can read Chinese and if you can’t just use Google translate)
Who are ROC nationals?
中華民國憲法 第3條
具有中華民國國籍者為中華民國國民
ROC nationals are people who have ROC citizenship, vice versa.
Are mainland Chinese people (大陸地區人民/mainland residents) ROC nationals?
法務部（85）法律決字第08886號
說明二：…故大陸地區人民得依上開規定認定具有中華民國國籍…
法務部 法律決字第16337號
大陸地區人民亦為中華民國人民
台北高等行政法院 民國90年 第4636號判決
大陸地區之人民依中華民國憲法仍是中華民國之國民
大陸地區人民非中華民國之外國人
經濟部智慧財產局 97.11.07. 電子郵件字第971107a號
大陸地區人民，依照「臺灣地區與大陸地區人民關係條例」既為中華民國人民
According to various explanations, judgements and the constitution of ROC, yes.
https://www.immigration.gov.tw/5385/7244/7250/20406/7326/36515/
（2）大陸地區人民：本署核發之入出境許可證件或大陸地區居民身分證。
Entry and exit permit for Taiwan is issued only to mainland residents and is a form of accepted form of identity documentation to apply for a national ID number like number by the Ministry of Interior. So this should be an acceptable proof for ROC nationality as the Ministry of Interior both governs the issuance of ROC nationally certificates and issues the entry and exit permit.
The email went out today and for complex matters, it could take up to 30 working days (about 6 weeks) so I’ll be updating you guys when I’ve got the reply.
I have more cases supporting my claims, I’ve basically have searched up all information related to ROC nationality for PRC nationals.
This said, I have not found any case of former PRC nationals obtaining ROC passports since the change in the nationality law which disqualified overseas Chinese to obtain ROC passports on the sole basis of Chines ethnicity.
fify.
Fyi
政治法律分析：陸客為國民？亦適用國家賠償法？
入出國及移民法第3條更規定，我國國民是指具有中華民國（本文亦簡稱我國或台灣）國籍之居住台灣地區設有戶籍國民或台灣地區無戶籍國民。
Eta: link may be not working well. How is this one? To the same article.
There is a path to citizenship for PRC spouses. Some take it, some don’t.
There is also a path based on parents. But none based on grandparents.
I’ve also read the case that you mentioned. It’s interesting because I have found conflicting viewpoints towards that particular case, with conflicting supporting evidences.
The most interesting part is mainland residents who are living overseas but haven’t obtained overseas citizenship yet. They are legally mainland residents, who by definition, does not have household registration in Taiwan area. The law counts overseas NHOWRs are ROC nationals. So from a legal standpoint, mainland residents living overseas are NHOWRs?
Btw there is also this explanation from the Ministry of Interior
內政部警政署入出境管理局 88.09.17.（88）境行順字第77729號
說明二：大陸地區人民旅居國外者，如符合旅居國外四年以上，且取得當地國籍者或取得當地永久居留權並領有我國有效護照者之條件，其身分即為臺灣地區無戶籍國民…
Not if they have a household registration / passport
if they meet those conditions.
The ministry of interior later published this explanation 台內戶字第 09400762762 號函, which can be found in this same post
I’ve read some documents that claim this overrides the one I’ve sent out, but it only made status changes to the Hong Kong and Macau residents and says mainland residents are ‘allowed’ to be naturalised as their new nationalities, making no mention at all regarding the NWOHR status.
So I wonder whether the one I’ve sent out is still in force? Or it’s no longer the case, this has been confusing me.
What is even more interesting is this explanation was published before the nationality changed, disqualifying anyone who merely has Chinese blood to become ROC nationals, now you need to be a decent of a ROC national to have ROC nationality instead of just being of Chinese ethnicity. So could it be the explanation I sent out is based on the former nationality law?