Hi Gerd,
well setting initial search limit to 1000000 solves already loads of bad solutions and is still quite fast. Albeit using v 408 it was the best universal value I felt. Not much slower but in many cases getting better results. Going for much bigger initial value actually then caused also worse splits. I do not know how right now it determines the max value. but maybe increasing it would be good. And I feel it should increase/wait if the split obviously is not good. If it is good (all tiles except one within 80% of maxnodes) or very good (all except one 85%) it could stop earlier in order not to waste resources.
I do not know how easy such a solution is to be implemented however. So far most bad splits are really realy bad (e.g. Norway 210 vs 135 tiles - in such cases a much longer time taken to find a good split is reasonable. Also as mkgmap will run faster if the split is better, compressing the maps will produce a smaller overall size if the split is better.