Probably too late now…
But I can confirm, it really is very difficult to convert NT$ to VND in Vietnam. It was easier in the past than now. The Dong is more stable than it used to be. For example 5 years ago, 1US$=VND15,780. This has slipped to the present rate of VND16,650 - a decline of 5%. It was around VND10,000 during my first trip there at the end of 1993. I have long since stopped worrying about holding some dong and sometimes return to find it has appreciated in my absence.
If you really must change NT$ in VN, then go to a jewellery shop, or a private forex dealer working out of a shop. You will get a poor rate, though. Don’t change it on the street. The best rate I got for some visiting Taiwanese when I worked there a few years back was around VND450/NT$1. Going via USD would have got about VND480. Believe it or not, one way this stuff gets changed, is via VN Airlines cabin crew hand carrying the NT$ on flights here and changing it at the airport back to USD which they take back to Vietnam the next day.
USD, GBP, EUR, JPY are the best. For changing USD, I would take US$50 or US$100. Some places give a better rate for these. Even if you have to buy these in Taiwan before you go just to change them when you arrive, then do this rather than take NT$. OR consider using ATMs in Vietnam. But they do charge. The charge is not high (can’t remember - maybe VND20,000), but most machines will only dispense VND2M at one time (roughly NT$4000). This is because they will only dispense 40 bank notes in one transaction. Some dispense VND100,000 notes, but seem to be restricted to dispensing 35 of them (ie VND3.5M). There is a machine at the airport in Saigon just after the x-ray as you leave the customs hall. For changing your USD, pretty much all banks give the same decent rate. The forex counter at the airport at Saigon gives a poorer rate, but it is still cheaper to change some USD there, and use a meter taxi on a meter in VND, than pay in USD. If you’re being collected, then change the money in the city centre.
Generally when shopping, I would use VND. Using USD is asking to pay more - though you might feel the numbers are easier to handle. The exception is hotels, where rates are usually quoted in USD. If you pay in VND, you might lose a little, but generally they are pretty honest in doing the conversion. If you pay by credit card, all except the “major hotels” will insist you pay 2% to 4% extra to cover credit card handling.
Don’t forget to leave enough cash to pay airport tax on departure. From memory, USD12 in Saigon. You can pay this in VND too. The equivalent - around VND200,000 is posted on a sign at the top of the stairs after customs and before immigration. They will round any change in their favour! Be warned: some Taiwanese told me they were ripped off here - they were told they could pay in NT$ and then charged NT$2000 each…