I can't give you your desired "most general" theorem, but I can say a little about this. In (b), the condition "shape(A) is lexicographically larger than shape(B)" is much stronger than it needs to be: "shape(A) is not dominated by shape(B)" will yield the same conclusion (recall the dominance order on partitions: $\lambda$ dominates $\mu$ if $\lambda_1+\cdots+\lambda_i\geqslant\mu_1+\cdots+\mu_i$ for each $i$).
To prove this: suppose all the entries in each row of $A$ are in different columns of $B$. Replace each entry of $B$ with the number of the row in which it appears in $A$; then by assumption the entries in each column of (the modified) $B$ are distinct. So if we sort the entries in this tableau into increasing order, all the entries less than or equal to $i$ will appear in the top $i$ rows. Hence the number of positions in the top $i$ rows of $B$ is at least the number of entries in the top $i$ rows of $A$, i.e. $\lambda_1+\cdots+\lambda_i\geqslant\mu_1+\cdots+\mu_i$ (where $\lambda=\operatorname{shape}(B)$ and $\mu=\operatorname{shape}(A)$).
This is all assuming that $A$ and $B$ have the same size. If $A$ is bigger than $B$, then obviously it goes wrong (because then $\lambda$ can't possibly dominate $\mu$, but the conclusion could easily be false). A more general statement (I think) is the following:
if either ($|\lambda|\geqslant|\mu|$ and $\lambda\ntrianglerighteq\mu$) or ($|\lambda|\leqslant|\mu|$ and $\mu'\ntrianglerighteq\lambda'$) then there are two entries in the same row of $A$ and the same column of $B$.
(Here I'm still writing $\lambda=\operatorname{shape}(B)$ and $\mu=\operatorname{shape}(A)$, $\lambda'$ denotes the conjugate (=transpose) partition to $\lambda$, and $\trianglerighteq$ is the dominance order.)