Another option: start with points randomly distributed (but sufficiently far apart) on the edges of the rectangle, and draw a curve (as a smooth random walk or similar) from of each. Then, after a random length, split the curve into two and keep going, AND when two curves get sufficiently close to one another, make them attract each other until they connect. I think with some tweaking this could give some good results too. Then to work out which area a point is in you could use the even-odd rule with a few intersection tests or just a flood-fill algorithm, I don't know, maybe you don't even need that information. I think if you want to capture the wobbly curvy aspect you will need a lot of metaballs (which is basically what you're proposing, I believe), but I suppose it could work.

Just an idea though. Voronoi diagrams are nice too but they are not really organic as per your illustration, more like tilings, as they have straight edges.

Placing the N points randomly in the area, then, when trying to get from which area are a coordinates in the area, check the distance and influence of each point.

This is a good way to go, take a look at voronoi cells, it sounds like your approach and produces really good results.