For each 4-vertex polygon:
Compute an estimate of the centre of the rectangle, C, as the mean of the 4 vertices.
Compute an estimate of the diagonal length of the rectangle, R, as the mean of the four distances from the estimated centre to each point times two.
Compute an estimate of the rotation angle of the rectangle by taking the mean of the angle of the line between points 1 and 3 and between points 2 and 4. Or possibly the mean of (the mean of the angle between (1 and C) and (C and 3)) and (the mean of the angle between (2 and C) and (4 and C). Basically an estimate of the angle midway between the two diagonals.
Compute the rectangle aspect ratio by computing the average of the unsigned angles of a line from each point to the centre point and the rotation angle. So if the rectangle is square this is 45 degrees.
Compute all the four points from the knowledge of the centre, the diagonal length, the aspect ratio, and the rotation angle.
I think this is robust to any convex arrangement of four points - I don't know what it might do if given a concave polygon...
Any chance you can dump your sample data and I might try and code this up....