This sounds like a job for the postgresql database to me. It has a number of geometric data features (that I'm always looking for an excuse to play with some time).
There's a "box" datatype, defined by the two corners, e.g.
box '((9,10), (11,13))', and there's an "area" function, e.g. area( box '((9,10), (11,13))' ), and there's also an "&&" operator you can use to see if two boxes intersect (which could be used with the logical NOT, I would presume, to find non-intersecting boxes).
Off the top of my head I don't see an easy way to get what you want all in one query, but I would think you could write a query to give you the next smaller box that doesn't intersect the already selected boxes... then you'd just need to repeat that process N times.
