Hello Piscador,
I think you have chossen some adorable points for the caches. I am sure the places : Mui Ne / Phan thiet and Can Tho is the right place to hide a traditional cache, cause there are a lot of tourist tour operators like Sinh Cafe, TM Brothers or Hahn Cafe to provide those day trips down there. Vung Tau is suitable too, but I think you will need a motobike to go up the hills.
Would be nice to see some more "real" caches in Vietnam.
Cheers
Cyril
Germany