With a little preprocessing (blur then threshold), I get decent results with your maps (this is for the first one you posted):
[attachment=2206:voronoi-map01.png]
Granted, it's kind of ad-hoc, but it works.

Thanks again for all the help, I couldn't get the results that I wanted with the method you posted but it helped me come to a solution that's giving some nice results and is pretty fast. Thought it would be a good idea to post the results and algorithm.

For the algorithm:

Step 1: Flood fill from the tiles to their neightbours that have the same walk-ability as it, assigning a shared value, such that comparing the value of 2 tiles will tell whether they are connected. Also count the number of tiles for each connected unwalkable set and if the total is low, I used 172, designate that "region" a small obstacle.

Step 2: Same as your first step, calculate the [color="#1c2837"]8-connected tiles. Though having a cost of 14 when it moves diagonally[color="#1c2837"] and 10 otherwise. It also doesn't assign an initial value to those tiles marked as small obstacles in the previous step.

[color="#1c2837"]Step 3: Then in a loop, continue until there are no unvisited tiles remaining:

[color="#1c2837"]Find the tile with the largest clearance(distance to obstacle) that hasn't been visited yet. Propagate from it tile to it's neighbours in the same way as step 2, though only travel to the 4-connected tiles, using a [color="#1C2837"]Brushfire Algorithm to travel through the tiles with a larger clearance first, skipping those already marked as chokepoints. While traveling, store the last tile that had the lowest clearance along the current path.

[color="#1c2837"]At each step compare the clearance of the start tile, the clearance of the current tile and the clearance of the lowest clearance tile so far. If certain conditions are met the lowest clearance tile will be marked as a choke point. The check I have so far is if the lowest value is less that 85% of the start tile or 75% of the current tile, then it is a chokepoint. The tiles between the obstacles that form the chokepoint are then marked off in a straight line, and all tiles on the other side of the chokepoint are removed from the current brushfire search. Then the burshfire algorithm continues until it cannot spread to any more tiles due to unwalkable tiles or chokepoint tiles.
[color="#1C2837"]The loop then continues, giving you after each step all the tiles that form this Region, the "center" of this region(the original tile) and the chokepoints connected to this region.

I still need to tweak the choke point detection values, but here are the results so far:
http://laccolith.imgur.com/results