You can determine all the corners as a first step. You could, for example, do this by traversing the outline after you first found it or it might just fall off as a byproduct of how you represent your shape in the first place. In your example there would be a corner at x=2to3 and y=2to3 (bottom left corner of the red rectangle). Realistically, you can now probably go on and grow out rectangles from all found corner points, eliminate duplicates and be done with it. This is likely your fastest solution in most circumstances, because the algorithm is quite simple, as long as your total number of points is reasonable.

It might be possible to construct rectangles from your corners and combine them for more optimization. That should only be neccessary, if your number of points is very large or the shape is very complex. Something like constructing all the smallest rectangles formable from your corners (e.g. the small red area). Then you can combine them recursively with each other and incrementally arrive at a set of rectangles ever-increasing in size.

The main takeaway should be: All maximal rectangles must contain at at least one corner at its boundary. So you can reduce your set of possible starting points and make the set of starting points only dependent on the complexity of the shape.