This might seem like a simple question, but I am quite confused by it.
I understand that a $D \times D$ rank-deficient matrix $A$ will collapse all vectors $\mathbf{x} \in \mathbb{R}^D$ to a flat subspace within the $D$-dimensional space (i.e., a $3 \times 3$ rank-deficient matrix would map all vectors it transforms to a $2D$ plane, $1D$ line or $0D$ point within the $3D$ space).
The consequence of this is that it is possible to find a vector $\mathbf{v} \in \mathbb{R}^D$ orthogonal to this lower-dimensional subspace, such that $A\mathbf{v} = \mathbf{0}$. This would mean that $\mathbf{v}$ is in the $\textit{null space}$ of $A$.
Given that the columns of a matrix can be thought of as the "basis" vectors in the transformed space, I can understand why $\mathbf{v}$ would be orothogonal to all columns of $A$ (since no linear combination of the columns of $A$ could be used to produce $\mathbf{v}$).
Nonetheless, by nature of the matrix equation $A\mathbf{v} = \mathbf{0}$, one could infer that $\mathbf{v}$ is also orthogonal to all rows of $A$, since $\mathbf{0}_i = 0 = A_i\mathbf{v}$ (where $A_i$ is the $i^{th}$ row of $A$).
However, I have read in numerous places that a vector in the null space of a rank-deficient matrix is not necessarily orthogonal to the rows $\textit{and}$ columns of the matrix.
Would someone be able to shed some light on this?
A vector in the null space of a matrix is, as you explicitly wrote, orthogonal to each of its rows. However, a vector in the kernel need not be orthogonal to the image. Consider the matrix \begin{align} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}. \end{align} Each of its columns is in its null space!