I am in SE Asia at the moment (Chris Travers-- signed up on the site). If you need ideas regarding places let me know. I have contacts around, and there are great places like Lombok. The question becomes though how remote is remote.

There are nice islands near Padang, Sumatra too (and Padang is famous for its food). In terms of SE Asia, Indonesia and Malaysia both have lots of tropical islands, but there is always the Maldives and the Philippines too.