One thing i have been wondering about is the "..find the nearest clear cell.." thing and since the starting position of the blue square in all test are the one shown in screenshot 1, that when it try to find the closest free cell it tries to choose one inside the enclosed area, as they are is closer to the blue square starting position.
I think you've got it there but it's not the cell nearest to the player starting postion. It's the cell closest to the target that's not blocked and if that's inside the enclosed area then it can't find a path.
Closest cell is inside enclosed area:
<img src="https://dl.dropbox.com/u/8367729/construct/pics/pathfindingClosest1.PNG" border="0" />
Closest cell is outside enclosed area:
<img src="https://dl.dropbox.com/u/8367729/construct/pics/pathfindingClosest2.PNG" border="0" />