This answer is more or less just a formalization of the intuition put forward by Nick Gill in his answer. The beginning parts are mostly just formalities, so you can probably skip down to the diagram.
Let $C$ be an axis-aligned orthogonal polygon. Following Chaikan et al., we'll consider $C$ as a union of squares. For any square $x \in C$, we define $$R(x) = \{ y \in C \;|\; \exists \text{ a rectangle in $C$ containing $x$ and $y$}\}$$
with the understanding that $x\in R(x)$. Next, we define a pre-order $\leq$ on $C$ by $$ x \leq y \iff R(x) \subseteq R(y)$$
Let $x$ and $y$ form an anti-rectangle and let $R(z) \subseteq R(x)$. Then, we can show that $z$ and $y$ also form an anti-rectangle. It follows that given an anti-rectangle $\{x_1, x_2, \ldots, x_k\}$, we can find another anti-rectangle $\{x_1', x_2', \ldots, x_k'\}$ of equal cardinality where each $x_i'$ is chosen to be a minimal element such that $x_i' \leq x_i$. In fact, we can construct a maximum anti-rectangle by selecting one representative from each of the minimal equivalence classes (defined in the usual way by the pre-order).
It now remains to show that if $C$ does not contain any holes, then there exists at least one minimal corner square. We will actually show slightly more: that there is at least one corner square $x$ on a "support edge" (by Chaikan et al's terminology) such that $R(x)$ is a rectangle. Observe that if $R(x)$ is a rectangle, then $x$ is minimal; we leave as an exercise for the reader to construct an example that shows that the converse is false.
Each edge in $C$ can be categorized by the squares at its endpoints. An edge can have either two, one, or zero corners at its endpoints. In the terminology laid out in Nick Gill's answer, these would correspond to $RR$, $RL$ (or $LR$), and $LL$ edges respectively (also, $RR$ edges correspond to "support edges" in Chaikan et al's terminology).
The key lemma we will need is that if $C$ is a simple, orthogonal polygon then it has strictly more $RR$ edges than $LL$ edges. First, we'll take as given that there are strictly more $R$ corners than $L$ corners (again, as defined in Nick Gill's answer) in $C$. Let $rr$, $ll$, and $rl$ be the number of $RR$, $LL$, and $RL$ edges. We will now try to count the number of each type of corner via counting each edge. Each $RR$ edge we'll count as two $R$ corners, each $LL$ edge as two $L$ corners, and each $RL$ edge as one $R$ and one $L$ corner. Counting in this way, we end up counting each corner exactly twice. So, we have $2r = 2rr+rl$ and $2l = 2ll+rl$. Thus, $0 < 2r - 2l = 2rr - 2ll$ and hence there are strictly more $RR$ edges than $LL$ edges.
Consider the following diagram of an $RR$ edge:
The heavy black lines indicate known boundaries of $C$. The red squares, $x$ and $y$ are the corners of the $RR$ edge. The blue squares $a$ and $b$ are the edge squares directly above $x$ and $y$ respectively (i.e.: all the squares between $x$ and $a$ and between $y$ and $b$ are interior squares).
If there were no edge squares in the shaded region, then $R(x)$ would be a rectangle and we would be done. So, let $c$ be an edge square in the shaded region. Furthermore, we choose $c$ to one of the edge squares closest to the $xy$ edge (i.e.: $c$ is one of the southernmost edge squares in the shaded region). Call the edge corresponding to $c$, $E$. Note that while there may be more than once such edge, for our purposes we will only need to choose one.
We now infer that $E$ must be an $LL$ edge. By construction of the shaded region, the endpoints of $E$ must lie inside the shaded region (otherwise, it would violate one of the clear paths between $x$ and $a$ or $y$ and $b$). Thus, if one of the endpoints of $E$ were a corner, it would contradict the choice of $c$ as one of the southernmost edge squares. Finally, we see that $E$ can be uniquely identified in this way with the $RR$ edge corresponding to $xy$. Otherwise, it would once again contradict the choice of $c$ as closest to $xy$.
So, we conclude that any $RR$ edge where the corners are not minimal can be uniquely identified with an $LL$ edge. Since there are more $RR$ edges than $LL$ edges, one of them must contain a minimal corner.
