Guys,
hi nicolas, i think i just flamed your koh tao DM idea.
i did my DM in indo about 6 months ago.
i was on this small island called Pulau Weh off the north easter tip of sumatra. i know it is in the troubled Aceh province but i felt 100% safe all the time. it is possible to fly all the way there but more fun to take the ferry from Medan. the ferry costs US$7 and the flight US$40. i did my DM in 2 months (no rush at all) and 'worked' there for another 2 after that. also remember that the indo currency is so bad that you can live like a king for months!
now there are 3 dive shops on the island (used to be 2). they are on Gapang and Iboih beaches.
the diving here is the best i have ever done and the reef alive with colour. this guy who does photography in sipidan dived with me and says it compares favouribly. you get sharks, barracudas, manta rays, eagle rays, whale sharks, dolphins, turtles, huge gorgonians, many different morays incl ribbon eels, snappers, trevally, wicked nudibranches, napolean wrasse, bump head parrotfish, triggerfish (all types) and so much more. the water is warm, about 28 C and the vis about 15m plus! if there is a down side (i dont think so), its the current can rip through here during full moon, but it just adds to the adrenaline and makes u a better diver. there is also a deep wreck (54 meters) which you can dive as well.
the name of the diveshops are Rubiah Tirta or Stingray and Lumba Lumba.
ok, enough preaching and i must be off now.
cheers,
James