Further, if any three points are collinear and distinct, then the construction is impossible.  To see this, put a point anywhere on each of two opposite (ie, non-adjacent) sides of the square.  Connect them.  The resulting line does not cross either of the other two sides of the square.  (Only exception: if two of the points are the same, then they define one corner of the square, and the construction might be possible). 

Are there other constructions which are impossible?  I expect so.  For instance, consider x-y points (0,100), (0,-100), (1,0), (-1,0).  If (1,0) and (-1,0) are on opposite sides of the square, then the square is too small to include either of the other two points.  And if they are on adjacent sides of the square, then the square mostly lies above or below the x-axis, and cannot include both of the other two points.

I don't, at the moment, have a formula which can test whether or not the construction is possible for any given four points.  I have a suspicion, though.  Draw a convex hull around the four points.  This hull must be entirely contained within the square, except for the 4 points which are on the square.  Calculate the distances between the two pairs of opposite points.  In my example above, the distances are 2 and 200.  Call the distances a and b.  Call the side of the square s.  

Well,   a >= s >= a/sqrt(2).  And b >= s >= b/sqrt(2) 

So,  the maximum ratio of a/b occurs when s = a and s = b/sqrt(2).  and the minimum ratio of a/b occurs when  s = b and s = a/sqrt(2).  So, a/b must be between sqrt(2)/2 and sqrt(2) (inclusive).

Can the square always be drawn if a/b is between sqrt(2)/2 and sqrt(2) (inclusive).  I don't have a construction which proves it, but at least I have not ruled it out.