(Opening lines stolen from Henning Makholm) In the two colorings you give, each square is the corner of 4 different good rectangles. Clearly if there is a solution with more than 16 good rectangles, then there needs to be at least one square that is in at least 5 good rectangles.
By appropriate permutations of rows and columns (all of which preserve the good rectangles), we can arrange it such that this square is in the lower left corner -- a1 in chess notation. Without loss of generality we can assume it is black:
4 ? * * *
3 ? * * *
2 ? * * *
1 B ? ? ?
a b c d
To be part of at least five rectangles, a1 must have three whites in one direction, which might as well be the 1 row, and at least two whites in the other. Then five of the opposite corners must be black, including at least two in the same column.
4 ? * * *
3 W B * *
2 W B B *
1 B W W W
a b c d
If a4 is black we must have c3 and d2 black to give five rectangles from a1
4 B * * *
3 W B B *
2 W B B B
1 B W W W
a b c d
We do best to fill it in like this
4 B W W W
3 W B B B
2 W B B B
1 B W W W
a b c d
which only gives 12.
If a4 is white we can get as many as nine rectangles including a1 if we fill the rest with black, but that is all we get. We can get our five for a1 like this
4 W B * *
3 W B * *
2 W B B B
1 B W W W
a b c d
but the best we can do is nine
4 W B B B
3 W B B B
2 W B B B
1 B W W W
a b c d
or we have to have five blacks in rows 2 and 3
4 W * * *
3 W B B *
2 W B B B
1 B W W W
a b c d
and more whites in the stars won't help us. 16 is the best
The proof with the first coloring works for this particular problem. The proof for the second doesn’t. That’s really the end of the matter.
You can try to make the argument more formal if that makes more sense to you. Assign a coordinate to each square on the chessboard, so that the top left corner is at $(1,1)$, and the bottom right corner is at $(8,8)$. The “white” squares will now correspond to the squares whose coordinates add to an even number, while the “black” squares will have coordinates that add to an odd number. It’s easy to see that when we remove both previously mentioned corners, we’re left with $32$ black squares, and $30$ white squares. However, a domino, which spans two adjacent squares, must necessarily cover both a white and a black square. Therefore, any valid covering must cover the same number of white and black squares, which means it’s impossible to cover up the whole mutilated board.
Your second coloring not working is just a consequence of the proof above not working for the corresponding modified definitions of the “white” and “black” squares. But a proof not working does not at all imply that another one is false.
Best Answer
If $m=n$, then $m$ and $n$ are both even or both odd; however, the condition requires an even number of black and white squares, so $mn = m^2$ is even; therefore $m=n$ is even. Now let's deal with rectangles that are not squares. Without loss of generality, $n<m$.
Lemma. Assuming $n < m$, the top $n$ rows form an $n\times n$ sub-board symmetric about its main diagonal.
Proof. Induct on the anti-diagonals, looking at them in the following order:
We begin in the middle of each anti-diagonal:
Then we work outwards, and every step is forced, so the anti-diagonal is symmetric. $\square$
The top $n \times n$ sub-board is symmetric, and its rightmost edge consists of $n$ squares on the edge of the board; its bottom edge (the $n^{\text{th}}$ row of the board), on the other hand, has $n$ squares with more squares below them. However, since the two edges are the same, the coloring condition for them is satisfied just by the $n \times n$ sub-board. Therefore the squares in the $(n+1)^{\text{th}}$ row are identically colored to the squares on the $n^{\text{th}}$ row.
It follows that if we delete the $n \times n$ sub-board, we get an $(m-n)\times n$ board for which the coloring condition also holds.
Now we can finish the claim by induction on the size of the board. The induction hypothesis tells us that both $m-n$ and $n$ must be even; therefore $m$ and $n$ are both even.