Wow. Scary how I've failed to do this until I ask the question on MO, and then immediately get the idea.

Here's a proof, assuming the weaker version of the theorem is true:

Call such an ordering "good." Consider a minimal counterexample $M$ of size $n$ to our stronger claim: it must be chordal, has a good ordering, but does not have a good ordering starting at every vertex. However, every chordal graph of size less than $n$ has a good ordering starting at every vertex.

Since $M$ has some good ordering $T$, it has some vertex $v$ (the last one in $T$) such that all its neighbors form a clique. Remove this vertex to get $M'$. $M'$ is chordal (since chordality respects vertex deletion), so we can make a good ordering starting with any element in $M'$. Attach $v$ to the end. This ordering is obviously still good. Thus, we can make a good ordering starting with any vertex that is not $v$. So it suffices to make a good ordering starting with $v$.

To do this, consider the last vertex $w$ in $T \setminus v$ with the property that $w$ is not connected to the vertex $w'$ immediately following it in $T$. If $w$ doesn't exist, this just means $M$ is a clique, so any ordering is good and we have a good ordering starting with $v$. If $w$ exists, then notice that $w$ cannot be connected with any of the vertices after it in $T$; if it is, then pick the earliest such one $u \neq w'$, which is both connected to the vertex directly preceding it (not connected to $w$ by choice of $u$) and $w$, a contradiction on the ordering being good. Thus, $w$ is only connected with vertices preceding it. This means all of $w$'s neighbors form a clique. Hence, we can delete $w$, make a good ordering starting with $v$ of the rest, and append $w$ to the end. A winner is us.

-Yan