Needing proof of convergence for a sequence
Let me first discuss the special case where $|u_n|$ is bounded. Let's denote our matrices by $A_n=\sum_{j=1}^n u_ju_j^*$. What we're trying to show can only fail if there are infinitely many $u_n=c_nv_n + w_n$ that have a coefficient $|c_n|\ge\delta >0$ when expanded in terms of the eigenvectors of $A_n$, such that the corresponding eigenvalue $\lambda_{n}$ stays bounded.
By compactness, these eigenvectors $v_n$ converge to a vector $v$ on a subsequence. Then, however, $\langle v_n, A_n v_n\rangle$ will become large because each of the many summands $u_ju_j^*$ of $A_n$ with a $u_j$ that is as above (with a component $\ge\delta$ in almost the direction of $v_n$) makes a contribution $\gtrsim \delta^4$ to this quadratic form. So $\lambda_n$ can not stay bounded.
In general, if $|u|$ is large, then consider (writing $Q=uu^*$) $$ |A^{-1/2}u|^2 = |(Q+B)^{-1/2}u|^2 =\langle u, (Q+B)^{-1} u\rangle ; $$ this is bounded because $-1/z$ is operator monotone, so $B$ in the quadratic form can be essentially dropped (more precisely, replace it by $\epsilon B$).
In other words, $x_n=A_n^{-1/2}u_n$ is always bounded, and we still find ourselves in the same scenario as above: to prevent $A_n^{-1/2}x_n$ from going to zero, $x_n$ and thus also $u_n$ must have a component bounded away from zero belonging to a bounded eigenvalue of $A_n$.
Thanks to Fedor Petrov for repeatedly pointing out my silly mistakes, and for suggestions how to improve the text (now I've rewritten the whole text).
$\let\eps\varepsilon\def\tr{\mathop{\rm tr}}\def\pr{\mathop{\rm pr}\nolimits}$ Denote $U_m=\sum_{i=1}^m u_iu_i^T$ ($U_m$ is regarded as a nonnegative self-agjoint operator in the Euclidean space). Set $f_m(x)=\langle U_mx,x\rangle=\sum_{i=1}^m\langle u_mx,u_mx\rangle^2$. By $\tr f$ we always mean the trace of the self-adjoint operator corresponding to a quadratic form $f$. Notice that $\tr f_m=\sum_{i=1}^m\|u_i\|^2$ and, more generally, $\tr f\big|_V=\sum_{i=1}^m\|\pr_Vu_i\|^2$ for every subspace $V$.
Let $\lambda_{1,m}\leq\dots\leq\lambda_{n,m}$ be the eigenvalues of $U_m$. Notice that $$ \lambda_{i,m}=\max_{V_{n-i+1}}\min_{0\neq x\in V_{n-i+1}}f_m(x)/\|x\|^2 =\min_{V_{i}}\max_{0\neq x\in V_{i}}f_m(x)/\|x\|^2, \qquad(*) $$ where $V_j$ is assumed to run over all $j$-dimensional subspaces. Since $f_m(x)$ does not decrease as $m$ grows, we have $\lambda_{i,m+1}\geq \lambda_{i,m}$ for all $m$. Moreover, $\lambda_{1,m}\geq c>0$ for sufficiently large $m$ (and some constant $c$), and we consider only much larger values of $m$. Finally, notice that for every $V_j$ we have $$ \lambda_{1,m}+\dots+\lambda_{j,m}\leq \tr f_m\big|_{V_j} \leq \lambda_{n-j+1,m}+\dots+\lambda_{n,m}. $$
Assume that the claim does not hold. We first show that $\lambda_{1,m}$ is bounded, and then show why it is impossible.
1. Assume that $\|U_m^{-1}u_m\|\geq \eps$ for some $m$. Set $v=U_m^{-1}u_m$, $w=U_{m-1}v$, $\alpha=\langle v,w\rangle=f_{m-1}(v)\geq \lambda_{1,m-1}\|v\|$ (so $\alpha$ is bounded away from $0$). Then $u_m=U_mv=w+\langle v,u_m\rangle u_m$ is collinear with $w$, $u_m=\beta w$. Now we have $\beta w=w+\beta^2\alpha w$, so $\alpha\beta^2-\beta+1=0$, $\beta=(1\pm\sqrt{1-4\alpha})/2\alpha$. This means that $\lambda_{1,m}\leq \alpha\leq 1/4$. So $\lambda_{1,m}\leq 1/4$ always. Moreover, $\beta$ is bounded away from $0$, as well as bounded from above (since $\alpha$ is not very small). Thus $f_m(v)=\langle v,w\rangle+\langle v,u_m\rangle^2=\alpha+(\beta\alpha)^2$ is also bounded by some constant $C_1$.
2. Let $e_1,\dots,e_n$ be the orthonormal base in which $U_m$ diagonalizes as $\mathop{\rm diag}(\lambda_{1,m},\dots,\lambda_{n,m})$. Consider the expansion of $v$ in this base. Since $\|v\|\geq \eps$ and $f_{m}(v)\leq C_1$, some eigenvector $e_i$ with eigenvalue $\lambda_{i,m}\leq 2C_1/\eps=:C$ appears in this expansion with a coefficient $\mu$ which is bounded away from $0$. Then $\langle e_i,u_m\rangle=\mu\lambda_{i,m}$ is also bounded away from $0$ by some $\delta>0$.
Set $V_i$ to be the span of $e_1,\dots,e_i$. Then $$ \lambda_{1,m}+\dots+\lambda_{i,m} =\tr f_m\big|_{V_i}=\tr f_{m-1}\big|_{V_i}+\|\pr_{V_i}u_m\|^2 \geq \lambda_{1,m-1}+\dots+\lambda_{i,m-1}+\delta^2. $$ This means that there exists some $k$ such that $C\geq \lambda_{k,m}\geq \lambda_{k,m-1}+\delta^2/n$. But such event (a small eigenvalue increases by at least $\delta^2/n$) may happen only finitely many times --- a contradiction.