Hi again,
I've been investigating some more and using mapshapper I've been able to narrow it down a bit.
I found two simplified versions of the original shape, one of them can be indexed correctly the other cannot be indexed. See the following gists:
If I superimpose the two shapes, it looks like this:
The green shape is the one that can be indexed, the red one the "bad" one.
Comparing the two raw JSON files it turns out that the only difference between them is the extra point in the red shape, all other points are exactly the same.
What's disturbing me is that It doesn't seem to fall in the four constraints you mentioned in your first reply. Maybe you have a clearer of idea of what exactly is going on. Is it that the Tesselation ends up creating too small a triangle ? My understanding of the ear-clipping algorithm is shallow...
Thank you for your help.