Is it possible to flip it around and create the land map from provinces instead of trying to break-down a pre-existing land map?
That's what I ended up doing in my title to avoid having to solve this problem. My landmass generation looks something like:
for (number of provinces that I want)
1. Pick a single sea cell as a start point (after rolling a dice to decide whether to start attached to existing land, or start a new island)
2. Grow the new province, adding one extra sea cell at a time until its a suitable size
3. If we managed to grow large enough, then accept it, otherwise back to #1 to pick a new start point.