Maybe (repeat, maybe) first find the bounding rectangle, regardless of area, as described by "Mandrill" above (who apparently overlooked your "given area" constraint). Then your "given area rectangle" will be inside that. Or, if that bounding rectangle is already your given area or less, then you're done. If not, choose any corner, and start moving it "inwards" in x, losing one point for sure, until you hit a second point. Then move it "inwards" in y until you again hit a second point. So that shrinks the rectangle as much as possible, while losing only the outermost point with respect to the selected corner. Save the resulting area. Now re-start with the original rectangle, and try each of the three other corners in turn. So you'll have four rectangles, each with one point lost. Choose the minimum-area rectangle from among these four. And now start again with that rectangle. Etc,etc, until you get the requisite area.
Now, this will certainly get you a "local minimum". But I'm not at all sure it'll get you the "global minimum".