Just a few things were clear right from the start:
- warm water diving please (we can have cold water diving all year ´round here in Germany...)
- lots of fish and nice coral (try out the new digital camera and housing)
- short boat rides to the dive spots (no sea sickness)
- at least three weeks long (the long flights (10 - 15 hours) to Asia almost kill you, so you'll need some rest)
- a nice, small island with a beach (just like on a postcard...)

So we went to the local travel agents and got some catalogues, surfed the WWW and spoke to some of the german travel agencies specialized in dive vacations.

Some places came to our minds and our favorite place almost changed by the hour: 
Bali - no, too many loud tourists in the north and not enough dive spots in the south. 
Thailand - either too many tourists or not too good visibility or too long boat rides. 
Indonesia - hmm not too bad, but where to go there?
PNG - too costly
Malaysia - yeah, sounds good!
"Wait, the other day I saw something in a catalogue about a small island called Lankayan. That could be something for us. Let's have a closer look! Well, not too much on the WWW about it, seems to be kind of a "good kept secret" - even more promising! Hey, on www.lankyan-island.com they say something about whale sharks and that the time of the year when we plan to travel  would be the best for seeing them. The rooms look nice, food is said to be very good, the island itself is not too big (just 10 bungalows, that means no more than 30 to 40 guests at a time. The island looks like it should with a beach around it, the boat rides are short (from 5 to 15 minutes), no-limit-diving is even included in the price - I think we've found what we were looking for! And due to the boat ride to the island which can not be at night we have to stay one night at a place called "Sepilok Nature Resort", where they raise orphan Orang-Utans - that must be nice to see and we will need some rest anyway after more than 12 hours cramped in an airplane."
Then we decided on the dates for the vacation and the details (e.g. on our way back home a stop over in Kuala Lumpur) and asked the travel agents for their prices and availability for our "dream-holidays". The prices did not differ very much (around 100 EUR total) but one of the travel agents at first seemed  to be more eager than the others and since it was the one with the lowest price anyway we choose it. Well at first they were eager, but only to the moment they got our money on their bank-account - but that's another story I'm not going to tell here. Should anyone be interested in detail, let me know...