I have tried that and it is hopeless just as you says. I also have tried several other programs but nothing works like in max. Is max really the only one that can do it? (Quadrangulate a flat mesh that is). BTW there is a better way in Maya,
Bring in the flat version of the mesh.
Select the border edges. (double click the border edged)
Convert to a curve. set to linear (Modify/convert/ edges to curve)
Then select the curve and convert to planar (surface/planar)
Set to polygon quad output and poly count.
But still the borders will not be so nice as in max, frustrating!