Looking for the minimal box with unconstrained rotation is a fairly hard problem. I don't know a solution off hand, but I can suggest a few potential avenues:

• Perform a linear regression of the points to determine a primary axis for the bounding box -- this isn't a minimal solution, but probably a reasonable approximation for relatively low cost. Once you have the axis, project the points into that frame of reference, compute the box as you would an AABB, then unproject the box back to the original space.
• Compute the convex hull of the set of points to reduce the number of points you need to consider. Once you have the hull, compute the minimal bounding box using an edge as one of the edges of the box, repeat for all edges, and choose the smallest box that results. To make calculating the boxes easier, for each box calculation project the hull into a frame of reference defined by the edge and compute as an AABB, store the edge index and area of the result somewhere, use the area to compare against other boxes, choose the winner, and only unproject the winner. This is most like your idea, but optimizes away degrees of rotation that aren't useful and also is truly minimal, choosing an arbitrary 180 rotations is not necessarily the absolute minimum (though the error is probably pretty small). Anyways, the hull-optimized version is almost certainly faster.
• If perfect or consistent results aren't required, consider early-outing if a potential match is below some threshold -- say by comparing the area of a potential bounding box to the area of the space enclosed by the convex hull using some heuristic, and just choosing it if it seems close enough for your purposes.

These techniques could be combined in various ways -- the second ought to give true minimum, but is costlier than the others.