Does the landing visa in your post mean a visitor visa? You may need almost the same hassle. The difference may be just doing it in or out of taiwan.
ROC Travel Authorization Certificate allows your wife to stay for 30 days, right? If it is not extendable, you should finish everything within the period, so anyway, it seems better to prepare documents before you will move in Taiwan.
How does a foreigner renew or apply for an ARC?(Serial No. 0902)
Instructions for Application for Residency Status by Foreign Nationals with Visitor Visas(Serial No. 0915)
Resident Visas for White Collar Workers
“Applicants who enter the R.O.C. (Taiwan) on a non-extendable Visitor Visa for the purposes of employment, investment, business or tourism may apply for a Resident Visa 7 work days before the duration of stay expires. The applicants may apply, without having to leave Taiwan, to the Bureau of Consular Affairs or any of its Central, Southwestern, Southern, or Eastern Taiwan Offices.”
“Applicants who enter the R.O.C. (Taiwan) without a visa and have obtained a work permit issued by competent authorities of the R.O.C. (Taiwan) may apply to the Bureau of Consular Affairs or any of its Central, Southwestern, Southern, or Eastern Taiwan Offices for an extendable Visitor Visa. Subsequently and with the extendable Visitor Visa, the applicants must apply to the National Immigration Agency for an Alien Resident Certificate.”
Countries eligible for Visa-exempt entry(Serial No. 0909)
"b However, aliens entering the R.O.C. through visa-exemption may apply for a visitor visa within the visa-exemption period on the following conditions at the Bureau of Consular Affairs and branch offices of MOFA.
ii white- collar professionals obtaining the work permit within. the visa-exemption period, plus their spouse and minors (under age 20) entering the R.O.C. together."