Is this combinatorial optimisation problem similar to any known problem?
You could formulate this as a gigantic integer linear programming (ILP) instance, and then apply an off-the-shelf ILP solver (lp_solve, CPLEX, etc.).  They will give you the best solution they can find.  Given the size of your problem instance, I don't know whether this will be efficient enough, but it would be easy to try.

Here's the ILP formulation.  We have a zero-or-one variable $x_r$ for each possible rectangle $r$, with the intended interpretation that $x_r=1$ means you include rectangle $r$ in your set and $x_r=0$ means you don't include it.  You want to maximize the objective function $\sum_r c_r x_r$ (where $c_r$ is the profit of rectangle $r$), subject to the restriction that $\sum_r x_r = n$ and that no two rectangles overlap.  The latter restriction can be expressed as a linear inequality by requiring $x_r + x_s \le 1$ for all pairs of rectangles $r,s$ that overlap.  So, in this way you get a ILP.