As it happens, there are indeed limits to how different the directions of $\vec L$ and $\vec \omega$ can be. This is because the moment of inertia tensor is something called positive semidefinite, which requires the inner product of any vector $\vec\omega$ with its transformation under the tensor, $I\vec\omega$ to be non-negative:
$$
\vec\omega \cdot I\vec\omega \geq 0.
$$
In particular, this means that the angle between $\vec L$ and $\vec \omega$ cannot be greater than 90°.
The moment of inertia, as a matrix, is normally defined with the components
$$
I_{ij} = \sum_k \left(r_{(k)}^2\delta_{ij} -x_i^{(k)}x_j^{(k)}\right)m_k
\tag 1
$$
for a cloud of particles with masses $m_k$, or as the integral
$$
I_{ij} = \int\left(r^2\delta_{ij} -x_ix_j\right) \rho(\mathbf r)\mathrm d^3\mathbf r
\tag 2
$$
for a continuous mass distribution. Normally you calculate the components about the principal axes of the moment of inertia, which is a frame in which the off-diagonal components like
$$
I_{xy} = -\int \,xy\,\rho(\mathbf r)\mathrm d^3\mathbf r
$$
vanish, and you're only left with the more usual diagonal components of the form
$$
I_{xx} = \int \left(y^2+z^2\right)\rho(\mathbf r)\mathrm d^3\mathbf r.
$$
In the general case, however, one needs to stick with the full matrix expressions $(1)$ and $(2)$, and it is not immediately obvious how one can prove from those expressions that the moment of inertia is positive semidefinite, so it is worth exploring that in a bit of detail.
(In a frame aligned with the principal axes this is easy, since in that frame you have
$$
\vec\omega \cdot I\omega
=
\sum_j I_{jj}\omega_j^2 \geq 0
$$
as all the $I_{jj}$ are non-negative. However, the existence of such a frame is not a trivial fact - it essentially requires us to know that the matrix $I_{ij}$ is diagonalizable and to find such a diagonalization. As such, it is better to work in the general case.)
The main point about the positive semidefiniteness of $I$ is that it encodes a much simpler relationship than its components lead you to believe. To see this relationship, you start with the fundamental definition of the angular momentum of a single particle,
$$
\vec L= \vec r \times \vec p = \vec r\times m\vec v,
\tag 3
$$
and then you use the fundamental definition of the angular velocity vector - that any particle rotating about the origin with (vectorial) angular velocity $\vec \omega$ will have velocity
$$
\vec v = \vec \omega \times\vec r,
\tag 4
$$
and you put this into the expression for the angular momentum:
$$
\vec L = \vec r\times m(\vec \omega\times\vec r).
\tag 5
$$
This looks complicated, but the key thing to realize is that it is linear in $\vec\omega$: if you put in a linear combination like $a_1\vec\omega_1 + a_2\vec\omega_2$ in for $\vec\omega$, you will get out $a_1\vec L_1 + a_2\vec L_2$. The equation above is a linear relationship between two vectors, and all such relationships can be expressed in matrix form:
$$
\vec L = I \vec \omega.
$$
The moment of inertia tensor is exactly that matrix.
However, the matrix form of the relationship is not necessarily the most useful way to phrase it. As an example, let me show the proof that $I$ is positive semidefinite, directly from the relationship $(5)$ above. I want to show that $\vec\omega\cdot\vec L\geq 0$, so I start by calculating that inner product:
\begin{align}
\vec\omega\cdot\vec L
& =
\vec\omega\cdot\left(\vec r\times m\,\vec v \right)
\\ & =
m\vec r\cdot\left(\vec v\times \vec\omega \right)
,
\end{align}
where I've used the cyclical property of the scalar triple product, because the cross product $\vec v\times \vec\omega$ is easy to calculate since $\vec v$ and $\vec\omega$ are orthogonal by construction. Putting in the definition $(4)$ for the velocity, we get a vector triple product, which is again easy to resolve:
\begin{align}
\vec\omega\cdot\vec L
& =
m\vec r\cdot\left((\vec \omega \times\vec r)\times \vec\omega \right)
\\ & =
m\vec r\cdot\left(\omega^2\vec r - (\vec\omega\cdot\vec r)\vec \omega \right)
\\ & =
m\left(\omega^2 r^2 - (\vec\omega\cdot\vec r)^2 \right)
.
\end{align}
Here we're essentially done, because we know that $|\vec\omega\cdot\vec r|$ must be no larger than $r\omega$, so we get the desired $\vec\omega\cdot I\vec \omega = \vec\omega\cdot\vec L \geq 0$. Finally, if we have a cloud of particles or a continuous mass distribution, we simply sum or integrate over this inequality.
OK, so the above is a (long-winded) explanation of why this $I$ matrix thing obeys this positive-semidefinite property. What does this mean geometrically? Well, expanding the inner product into an angle form, it gives us
$$
\vec\omega\cdot\vec L = \omega L\cos(\theta)\geq 0,
$$
where $\theta$ is the angle between the angular momentum and the angular velocity; this inequality translates into $\theta \leq \pi/2=90^\circ$.
This bound is pretty much the best you can do, and it is easy to find examples where $\vec \omega$ and $\vec L$ are arbitrarily close to orthogonal. The simplest is a long, thin rod of length $L$ and radius $w$ that's rotating rapidly about an axis that is almost (but not quite) aligned with the rod:
Putting the rod along the $x$ axis, you get that the moment of inertia and angular velocity are given by
$$
I=
\begin{pmatrix}
\frac12 Mw^2 & 0 & 0 \\
0 & \frac13 ML^2 & 0\\
0 & 0 & \frac13 ML^2
\end{pmatrix}
\quad\text{and}\quad
\vec \omega=
\begin{pmatrix}
\Omega \\ \delta \\ 0
\end{pmatrix},
$$
respectively, and that gives you
$$
\vec L=
\begin{pmatrix}
\frac12 Mw^2\Omega \\ \frac13 ML^2\delta \\ 0
\end{pmatrix}
$$
for the angular momentum,
$$
\vec\omega\cdot \vec L = \frac12 Mw^2\Omega^2 + \frac13 ML^2\delta^2
$$
for the inner product, and
$$
\cos(\theta)
=
\frac{\vec\omega\cdot \vec L}{L\omega}
=
\frac{
\frac12 w^2\Omega^2 + \frac13 L^2\delta^2
}{
\sqrt{\frac14 w^4\Omega^2 +\frac19 L^4\delta^2}
\sqrt{\Omega^2+\delta^2}
}
\approx
\frac{
3 w^2/L^2 + 2 \delta^2/\Omega^2
}{
\sqrt{9 w^4/L^4 +4 \delta^2/\Omega^2}
}
$$
for the angle. Fixing the rod parameters at $w\ll L$, and then choosing an angular velocity with $\Omega\gg \delta$ and such that
$$
\frac wL \ll \frac \delta\Omega
$$
(i.e. the rod is much thinner than the spin axis is close to the rod axis), the cosine approximates to
$$
\cos(\theta)
\approx
\frac{\delta}{\Omega}
+\frac{3\,w^2/L^2}{2\,\delta/\Omega}
,
$$
which can be made arbitrarily small, with the angle
$$
\theta \approx \frac \pi2 -\left(\frac{\delta}{\Omega} + \frac{3\,w^2/L^2}{2\,\delta/\Omega}\right)
$$
arbitrarily close to 90°.
More geometrically, spinning a thin rod about its axis gives an angular momentum component along this axis which is very small, and any misalignment will give angular momentum describing rotation about the axis of misalignment which, if the rod is thin and long enough, can dwarf the angular momentum from the spinning itself.
Finally, it's important to note that the angular momentum and the angular velocity can never be fully orthogonal. This can be seen by expressing the orthogonality relation $\vec\omega \cdot \vec L=0$ in the principal frame of the body, where it takes the form
$$
\vec\omega \cdot \vec L
= I_{xx}\omega_x^2 + I_{yy}\omega_y^2 + I_{zz}\omega_z^2
=0,
$$
i.e. the sum of three non-negative terms, all of which must be zero for the sum to vanish. This is possible by having e.g. $I_{xx}=0$ and $\omega_y=\omega_z=0$, but in that case (and all such cases) you will obtain $\vec L=0$, which doesn't really count as "orthogonal" to $\vec\omega$.
Best Answer
OK, I think I figured it out -- it's not the rotation that is important, it is the fact that the "center of rotation" isn't at the origin any more.
Rather than think about the $\begin{bmatrix}1 & 2 & 3\end{bmatrix}^T$ that I had before as angular velocity, let's think about an easier case. Suppose we are rotating my point mass on the X axis around an axis rotated $45^\circ$ from the X axis. Because it will make the numbers come out easier, let's say that the point mass is at $x=\sqrt{2}$.
Now if we change our point of view so that our reference frame is parallel to the rotation axis, the point is no longer at $\begin{bmatrix} \sqrt{2} & 0 & 0\end{bmatrix}^T$, but is now at $\begin{bmatrix} 1 & 1 & 0 \end{bmatrix}^T$ in the new frame. In this frame, the inertia tensor will have one nonzero product of inertia:
$\mathbf{I}'=\begin{bmatrix}1 & -1 & 0 \\ -1 & 1 & 0 \\ 0 & 0 & 2\end{bmatrix}$
Now that it has a nonzero product of inertia, it makes sense that the angular momentum isn't parallel to the rotation any more.
I would have guessed that just sliding along the rotation axis wouldn't change the inertia tensor, but further consideration (and math) shows that it does. The inertia about the rotation axis we are sliding along doesn't change, but the inertia about other axes can, and therefore the inertia tensor will no longer be diagonal and the angular momentum will no longer be parallel to the rotation axis.