I'm looking to get prepaid SIM cards while I'm travelling in SE Asia this fall. How is the availability of micro SIM cards (i.e. the kind you use for iPhones) in Vietnam and Cambodia? And more specifically, in Hanoi and Phnom Penh. Is it regularly available or should I bring a phone that can use a regular-size SIM card?
I can't vouch for micro SIMs, but this wiki (very handy) will give you the lowdown on getting prepaid SIMs most everywhere you need to go. Shops or airport kiosks will probably know more about getting a micro SIM. If all else fails, though, you can use a SIM cutter.
I can't say about the smaller places, but in the big cities like Hanoi, Phnom Penh and Ho Chi Minh it's fairly easy to get the sim cards, both normal and micro SIMs.
It appears that the 3G network is also quite good, and not expensive. (check viettel.com for some information)
You should travel with a micro (or nano if you have an iphone) sim cutter. They are relatively cheap to obtain off ebay. This will make your life much simpler as you can obtain regular sim cards everywhere.