Divide grid so that each box has only one object
I initially missed your remark about overlapping rectangles -- as orlp said in a comment, there's obviously no solution in those cases.  But I had already typed the rest of this answer out, assuming the input has no overlapping rectangles, so I'll leave it here in case it's helpful.

It sounds like your current method repeatedly looks for a guillotine cut: That is, a cut that goes all the way from top to bottom, or all the way from left to right.

Unfortunately, even if you split subproblems at as many places as possible within a single $O(n \log n)$-time scan along one dimension, this can result in $O(n^2 \log n)$ time overall, like for instances such as the following where each scan only succeeds in peeling off a single rectangle:

XXXXX

X   X
X X X
X
X XXX


But the real problem is that some instances can't be solved this way at all, even when no overlapping rectangles are involved.  For example:

XXX X
    X
X   X
X
X XXX