I finally understand enough to answer my own question. Note that all rotations considered are rotations about (an axis through) the origin. Our discussion is strictly limited to these kinds of motions.
Before getting into the question, it needs to be said that it makes no sense to assign a single angular velocity to two particles unless more is specified (what are their masses? are they part of a rigid body? etc.). For this reason, we slightly modify the original scenario and assume the two particles are connected a massless rigid rod. This combines them into a 1D rigid object in which it makes sense to talk about the rotation of that object.
The ambiguity of the angular velocity vector persists, and I will explain exactly why it is there, and why it is not really a problem. The problem doesn't even pertain to just the angular velocity vector, but angular displacement as well, so for this reason I attached the following links to other posts of mine where I explain (one of various possible ways of talking about) angular displacements:
Explaining the Ambiguity
Consider the two particles
$$ \vec{r}_{1}(t) = (\cos ct, \sin ct, 1) \quad\text{ and }\quad \vec{r}_{2}(t) = (-\cos ct, -\sin ct, -1) $$
connected by a massless rigid rod.
The motion $\vec{r}_{1}(0) = (1, 0, 1)\rightarrow\vec{r}_{1}(t)$ and $\vec{r}_{2}(0) = (-1, 0, -1)\rightarrow\vec{r}_{2}(t)$ can be given by the rotation matrix
$$ R(t) = \begin{pmatrix} \cos ct & -\sin ct & 0 \\ \sin ct & \cos ct & 0 \\ 0 & 0 & 1 \end{pmatrix}, $$
but it can equally as well be given by
$$ S(t) = \underbrace{ \begin{pmatrix} \cos ct & -\sin ct & 0 \\ \sin ct & \cos ct & 0 \\ 0 & 0 & 1 \end{pmatrix} }_{R(t)}
\underbrace{ \begin{pmatrix} \tfrac{\cos(ct/\sqrt{2})+1}{2} & \tfrac{\sin(ct/\sqrt{2})}{\sqrt{2}} & \tfrac{-\cos(ct/\sqrt{2})+1}{2} \\ -\tfrac{\sin(ct/\sqrt{2})}{\sqrt{2}} & \cos(ct/\sqrt{2}) & \tfrac{\sin(ct/\sqrt{2})}{\sqrt{2}} \\ \tfrac{-\cos(ct/\sqrt{2})+1}{2} & -\tfrac{\sin(ct/\sqrt{2})}{\sqrt{2}} & \tfrac{\cos(ct/\sqrt{2})+1}{2} \end{pmatrix} }_{X(t)}. $$
Here $R(t)$ is a rotation about the $z$-axis. The matrix $S(t)$, on the other hand, represents a rotation $X(t)$ about the $(1, 0, 1)$-axis followed by a rotation $R(t)$ about the $z$-axis.
Here we immediately see the issue: because the two particles and the rod are always along a line through the origin, there is freedom in how we can rotate about that line without making any difference to the actual particles. This is the reason for the ambiguity in my original post.
If one calculates the corresponding angular velocity vectors (see above links for how to do this) we obtain
$$ \vec{\omega}_{R}(t) = (0, 0, c) $$
and
\begin{align}
\vec{\omega}_{S}(t) &= \vec{\omega}_{R}(t) + R(t)\vec{\omega}_{X}(t) \\[1.0ex]
&= (0, 0, c) + (-\tfrac{c}{2}\cos ct, -\tfrac{c}{2}\sin ct, -\tfrac{c}{2}) \\[1.0ex]
&= (-\tfrac{c}{2}\cos ct, -\tfrac{c}{2}\sin ct, \tfrac{c}{2}).
\end{align}
More generally, we have freedom to add any vector that is parallel along the line along which the particles line up, which is any scalar multiple of $(\cos ct, \sin ct, 1)$.
As soon as we introduce another particle whose position is linearly independent from the existing ones, the ambiguity and the degree of freedom in both the rotation matrix $R(t)$ and the angular velocity $\vec{\omega}(t)$ are lost!
Any rigid body with $\ge 2$ linearly independent points will have a uniquely determined rotation matrix $R(t)\in\textrm{SO}(3)$ and angular velocity $\vec{\omega}(t)\in\mathbb{R}^{3}$ for all $t$.
Thus, this is no issue for any 3D extended rigid body.
If we replaced our particles by extended spheres (whose points are distinguishable and can be tracked), we would have no ambiguity as to what $\vec{\omega}(t)$ would have been, because the different angular velocities would have produced different motions (in real life we could place a piece of tape to one of the spheres and $\vec{\omega}_{R}$ vs $\vec{\omega}_{S}$ would produce different traces of that tape).
Why This Ambiguity Makes No Difference for the Moment of Inertia
I also wanted to point out another interesting phenomena. So far we haven't considered the masses of our point particles, but let's say the two particles have some masses now. Even though the angular velocity of our object (two points connected by a massless rigid rod) has a degree of freedom, it makes no difference to the formula $\vec{L} = \overleftrightarrow{I}\vec{\omega}$ where $\vec{L}$ is the total angular momentum and $\overleftrightarrow{I}$ is the moment of inertia tensor, because $\vec{L}$ comes out exactly the same regardless of which $\vec{\omega}$ we use. This phenomena is explain in Part 3 of this post of mine here.
A Word About One Formula
For a point particle, or for any mass distributed along a line through the origin, one can set the angular velocity by the formula
$$ \vec{\omega} = \frac{\vec{r}\times\dot{\vec{r}}}{r^{2}}. $$
This is the unique angular velocity for which $\vec{\omega}\cdot\vec{r} = 0$ (this can be proven with some vector identities), i.e. the unique angular velocity for which there is component of rotation about the radial line that goes through the particle or mass.
This is convenient, but it's not always desirable to use. My original scenario is one example where it's not desirable, because this formula gives an angular velocity vector $\vec{\omega}$ that changes direction (so the axis of rotation constant precesses). On the other hand, if we add a component to $\vec{\omega}$ along the direction of the particles and massless rod, we can get $\vec{\omega}$ to be constant, giving us a more intuitive picture of what's going on: the system is rotating about the $z$-axis at angular frequency $c$.
Moreover, the formula does not apply to (points on) extended rigid bodies! If a rigid body exhibits a combination of an orbit about an axis through the origin and a spin about an axis through its center of mass, then we definitely don't have $\vec{\omega}\cdot\vec{r} = 0$ for points on the rigid body. Here are pages that discuss the formula and its issues:
The formula that does always hold is $\vec{\omega}\times\vec{r} = \dot{\vec{r}}$ where $\vec{r}$ is the position of a point particle or point on a rigid body.