I'm not involved in the multipolygon code at all, but some comments:
I realise that it would be easier if I made a drawing so look at http://www.mkgmap.org.uk/tmp/islands.png
In nicely working maps A and B are coincident, as are C and D. In our maps C and D are not, our original code also made them coincident, but this failed when the polygon was big enough to need splitting. This is why I suggest attempting to split large polygons first.
Reading this, it means for me, that the splitting code ist the source of the problems. Maybe we need an more complex code for splitting, which handles concave polygons well. I imagine something like cut it with a pair of scissors. But I have no algorithm at hand.
Point 3 is illustrated by the second diagram, where a sea polygon is split into X and Y and avoids the need for a DABC cut as in the first. It may not be easy to take advantage of this with an algorithm, but I'd probably make use of that a lot if doing it by hand.
Sorry, but I can't see the difference. The picture on the right side shows a splitted polygon, but there are two places with parallel lines. Both polygons have concave segments too. So there is the same need for a DABC cut. Where is my misunderstanding? Regards, Johann