All markers can be removed if and only if at least one of m, n is odd. Suppose WLOG m is odd and all boards of area less than mn with one of m, n odd satisfy the property. Then we can solve the m*(n-1) board, at which point we have a row of m black markers. We can remove markers 1, 3, 5, ..., m, and then 2, 4, 6, ..., m-1, which are all black now.
Suppose that m, n are even. The perimeter of the entire initial rectangle is 2(m+n). In particular, this is 0 mod 4. When a piece is removed, suppose it shares perimeter k with the entire figure. Then when it is removed, k is lost from the entire perimeter and 4-k is gained, for a net gain of 4-2k, or 2k mod 4. Now all but the original black marker k corresponds to the number of adjacent markers removed (always odd since the removed marker must be black) plus the perimeter the marker in question shares with the original rectangle (odd for edges, even for corners and centers). Hence the perimeter changes by 2 mod 4 each time a center piece or corner (other than the original) is removed. Thus the perimeter changes (n-2)(m-2)+3 times from 2(n+m). This would indicate that the final perimeter is 2 mod 4, but we know it should be 0. Contradiction.