Some thoughts; I am not $100\%$ sure yet and will revisit:
A bi-partite (pure) state $|\Psi\rangle \in \mathcal{H}_{A} \otimes \mathcal{H}_{B}$ is maximally entangled if the reduced state in either $\mathcal{H}_{A}$ or $\mathcal{H}_{B}$ is the maximally mixed state.
Suppose we have a state
\begin{equation}
|\hat{\Psi}\rangle = C \sum_{k=1}^{N}|u_{k}\rangle \otimes |v_{k}\rangle,
\end{equation}
where $\{|u_{k}\rangle\}$ and $\{|v_{k}\rangle\}$ may or may not be orthonormal. Lets assume that they are at least normalized.
Furthermore, let $\{|a_{j}\rangle\}$ be an orthonormal basis for $\mathcal{H}_{A}$.
The reduced state $\rho_{B} = \mathrm{tr}_{A}\big[|\hat{\Psi}\rangle\langle \hat{\Psi}|\big]$ on $\mathcal{H}_{B}$ is:
\begin{equation}
\begin{split}
\rho_{B} &= \sum_{j} \big(\langle{a_{j}}|\otimes I \big) |\hat{\Psi}\rangle\langle \hat{\Psi}| \big(|{a_{j}}\rangle\otimes I \big) \\
&= |C|^{2}\sum_{j}\sum_{k}\sum_{k'} \langle a_{j}|u_{k}\rangle \langle u_{k'}|a_{j}\rangle \otimes |v_{k}\rangle\langle v_{k'}| \\
&= |C|^{2}\sum_{k}\sum_{k'} \langle u_{k'}| \Big( \sum_{j}| a_{j}\rangle\langle a_{j} |\Big) |u_{k}\rangle |v_{k}\rangle\langle v_{k'}| \\
&= |C|^{2}\sum_{k}\sum_{k'} \langle u_{k'}| I |u_{k}\rangle |v_{k}\rangle\langle v_{k'}|. \\
\end{split}
\end{equation}
If we put the $\{|u_{k}\rangle\}$ and $\{|v_{k}\rangle\}$ in matrices $U$ and $V$:
\begin{equation}
\begin{split}
U &= \begin{bmatrix}|u_{1}\rangle & |u_{2}\rangle \cdots |u_{n}\rangle\end{bmatrix} \\
V &= \begin{bmatrix}|v_{1}\rangle & |v_{2}\rangle \cdots |v_{n}\rangle\end{bmatrix}
\end{split}
\end{equation}
we get for:
\begin{equation}
U^{\dagger}U = \begin{bmatrix} \langle u_{1}|u_{1}\rangle & \cdots & \langle u_{1}|u_{n}\rangle \\ . & \ddots & . \\
\langle u_{n}|u_{1}\rangle & \cdots & \langle u_{n}|u_{n}\rangle \\\end{bmatrix} = I + \hat{D}_{U}
\end{equation}
for some off-diagonal (Hermitian, likely sparse) matrix $\hat{D}_{U}$. We can do the same for $V$, getting $\hat{D}_{V}$
That allows us to write for $\rho_{B}$:
\begin{split}
\rho_{B} &= |C|^{2}\sum_{k}\sum_{k'} \langle u_{k'} |u_{k}\rangle |v_{k}\rangle\langle v_{k'}|\\
&= |C|^{2}\sum_{k}\sum_{k'} |v_{k}\rangle \langle u_{k'} |u_{k}\rangle \langle v_{k'}|\\
&= |C|^{2}VU^{\dagger}UV^{\dagger} \\
\end{split}
The question is now when this is or is not equal to the maximally mixed state i.e. $|C|I$ (note that the normalisation factor is different because we're in a smaller space!). We know, since $\{|u_{k}\rangle\}$ and $\{|v_{k}\rangle\}$ are in fact bases, both $U$ and $V$ are invertible, such that $\rho_{B} = |C|^{2}VU^{\dagger}UV^{\dagger}= |C|I$ implies that:
\begin{equation}
U^{\dagger} U = V^{-1} (V^{\dagger})^{-1} = (V^{\dagger}V)^{-1}
\end{equation}
up to some normalisation factor.
Lets investigate the three (without loss of generality) options:
The bases $\{|u_{k}\rangle\}$ and $\{|v_{k}\rangle\}$ are orthonormal.
Then, $U^{\dagger}U = V^{\dagger}V = I$ and the state is maximally entangled, as expected.
$\{|u_{k}\rangle\}$ is, but $\{|v_{k}\rangle\}$ isn't orthonormal.
Then, $U^{\dagger}U = I \not = V^{\dagger}V$. This shows that if only one of the bases is orthonormal, the state cannot be maximally entangled.
Both $\{|u_{k}\rangle\}$ and $\{|v_{k}\rangle\}$ aren't orthonormal. Then, $U^{\dagger}U,V^{\dagger}V \not = I $. The state might still be maximally entangled, as long as $U^{\dagger}U$ is the inverse of $V^{\dagger}V$, or in other words: $|C|U^{\dagger}UV^{\dagger}V = I$.
We can say a little more:
\begin{equation}
\begin{split}
I &= |C|U^{\dagger}UV^{\dagger}V\\
&= |C|(I + \hat{D}_{U})(I + \hat{D}_{V}) \\
&= |C|I + |C|\hat{D}_{U} + |C|\hat{D}_{V} + |C|\hat{D}_{U}\hat{D}_{V} \\
\end{split}
\end{equation}
Both $\hat{D}_{U}$ and $\hat{D}_{V}$ are purely anti-diagonal, which means that their product $\hat{D}_{U}\hat{D}_{V}$ has diagonal elements that are equal to $1-|C|$. The off-diagonal terms need to cancel out; in higher dimensions this could get messy.
Some extra thoughts about the bi-partite case
For a bi-partite state (and thus $\hat{D}_{U}\hat{D}_{V}$ purely diagonal) we get that $\hat{D}_{U} = -\hat{D}_{V}$, which means that
$$\langle u_{1}|u_{2}\rangle = - \langle v_{1}|v_{2}\rangle.$$
Moreover, for the bi-partite state we also get $\frac{1}{2}I = I + \hat{D}_{U}\hat{D}_{V}$ so that
$\hat{D}_{U}\hat{D}_{V} = -\frac{1}{2}I$ which leads to
$$\langle u_{1}|u_{2}\rangle \langle v_{2}|v_{1}\rangle = \langle u_{2}|u_{1}\rangle \langle v_{1}|v_{2}\rangle = -\frac{1}{2}.$$
You can combine this to say that $\langle v_{1}|v_{2}\rangle\langle v_{2}|v_{1}\rangle = \langle u_{1}|u_{2}\rangle\langle u_{2}|u_{1}\rangle = \frac{1}{2}$. This puts quite strong constraints on the bases.
Essentially, the bases provided by Daftwullies answer seem to be (up to permutations and some extra phases) the only ones.
The relation $U^{\dagger}UV^{\dagger}V = I$ can very well be met even if $U$ and $V$ are not unitary; we have (for the bases Daftwullie came up with):
\begin{equation}
\begin{split}
U &= \begin{bmatrix} \sqrt{2} & 1 \\ 0 & 1
\end{bmatrix} \\
V &= \begin{bmatrix} \sqrt{2} & -1 \\ 0 & -1
\end{bmatrix} \\
\end{split}
\end{equation}
which can be readily checked to obey $U^{\dagger}U V^{\dagger}V = I$:
\begin{equation}
\begin{split}
U^{\dagger}UV^{\dagger}V &= \begin{bmatrix} \sqrt{2} & 0 \\ 1 & 1
\end{bmatrix} \begin{bmatrix} \sqrt{2} & 1 \\ 0 & 1
\end{bmatrix} \begin{bmatrix} \sqrt{2} & 0 \\ -1 & -1
\end{bmatrix} \begin{bmatrix} \sqrt{2} & -1 \\ 0 & -1
\end{bmatrix} \\
&= \begin{bmatrix} 2 & \sqrt{2} \\ \sqrt{2} & 2
\end{bmatrix} \begin{bmatrix} 2 & -\sqrt{2} \\ -\sqrt{2} & 2
\end{bmatrix} \\
&\sim I
\end{split}
\end{equation}
The states also obey the above equations for the inner products in the bi-partite case.
Old incorrect analysis
Now I first wrote the text below, but this is actually incorrect. After the answer of DaftWullie it became clear that there actually are examples of this. My error in the below derivation is that the Frobenius inner product $2\langle VV^{\dagger}, V\hat{D}_{U}V^{\dagger}\rangle$ does not bear a square, and can therefore be negative. That means that the inequality actually does not hold.
I don't actually think that this is possible under the assumption that
all states need to be normalized. (which means, if you recall, that
$U^{\dagger}U = I + \hat{D}_{U}$ with that identity being, well, the
identity).
We already had $U^{\dagger}U = I + \hat{D}_{U}$, so that (using the
Frobenius norm): $$||U^{\dagger}U||^{2} = ||I + \hat{D}_{U}||^{2} =||I||^{2} + ||\hat{D}_{U}||^{2} + 2\langle I,\hat{D}_{U}\rangle_{F} = ||I||^{2} + ||\hat{D}_{U}||^{2} \geq ||I||^{2},$$ where $\langle I, \hat{D}_{U}\rangle_{F}$ is the Frobenius inner product, which is zero
here because $\hat{D}_{U}$ is by definition traceless. Moreover, the
inequality becomes strict when $\hat{D}_{U}$ is non-empty and
therefore $||\hat{D}_{U}|| > 0$ (the Frobenius norm is a norm). This
is only true if the basis encoded in $U$ is non-orthogonal.
For our relation $\rho_{B} = I = VU^{\dagger}UV^{\dagger} = V(I +
> \hat{D}_{U})V^{\dagger} = VV^{\dagger} + V\hat{D}_{U}V^{\dagger}$, we
get:
\begin{equation} \begin{split} ||I||^{2} &= ||VU^{\dagger}UV^{\dagger}||^{2} = ||VV^{\dagger} + V\hat{D}_{U}V^{\dagger}||^{2} \\ &= ||VV^{\dagger}||^{2} + ||V\hat{D}_{U}V^{\dagger}||^{2} + 2\langle VV^{\dagger},V\hat{D}_{U}V^{\dagger}\rangle \\ &\geq ||VV^{\dagger}||^{2} +
||V\hat{D}_{U}V^{\dagger}||^{2} \\ & = ||I ||^{2} + ||
\hat{D}_{V}||^{2} + ||V\hat{D}_{U}V^{\dagger}||^{2} \\ & \geq ||I
||^{2} + ||V\hat{D}_{U}V^{\dagger}||^{2} \\ \end{split} \end{equation}
with the second bound only an equality if $||\hat{D}_{V}|| = 0$, which
is not the case if the basis encoded in $V$ is not orthogonal. So
in that case we have $||I||^{2} \geq ||I||^{2} + || \hat{D}_{V}||^{2}
> + ||V\hat{D}_{U}V^{\dagger}||^{2} > ||I||^{2}$, which is a contradiction. We have to conclude that $\hat{D}_{V}$, and conversely
$\hat{D}_{U}$ are zero, which means that the bases must be orthogonal.