Counting the number of minimal covers of a binary matrix
It's easy to show that some inputs can produce an exponential number of minimum covers.  Consider the following 3x3 matrix:

110
100
000


This can be minimally covered in exactly 2 ways: either using a single vertical 2x1 rectangle and a single 1x1 rectangle, or a single horizontal 1x2 rectangle and a single 1x1 rectangle.

Thus placing $k$ non-overlapping copies of this gadget in a grid will produce an instance with $2^k$ distinct minimal covers.  You could, for example, tile an $n$ by $n$ grid with $n^2/9$ of them to produce an instance with $2^{n^2/9}$ minimal covers.

(It's possible that a better gadget exists -- that is, smaller gadgets that would increase the coefficient in the exponent.  More interestingly it's possible that instances with asymptotically more minimal covers exist.)