Bellman-Ford algorithm - Why can edges be updated out of order?
Consider the shortest path from $s$ to $t$, $s, v_1, v_2, \dots, v_k, t$. This path consists of at most $|V|-1$ edges, because repeating a vertex in a shortest path is always a bad idea (or at least there is a shortest path which does not repeat vertices), if we do not have negative weight cycles.

In round one, we know that the edge $(s, v_1)$ will be relaxed, so the distance estimate for $v_1$ will be correct after this round. Note that we have no idea what $v_1$ is at this point, but as we've relaxed all edges, we must have relaxed this one as well. In round two, we relax $(v_1, v_2)$ at some point. We still have no idea what $v_1$ or $v_2$ are, but we know their distance estimates are correct.

Repeating this, after some round $k+1$, we have relaxed $(v_k, t)$, after which the distance estimate for $t$ is correct. We have no idea what $k$ is until the entire algorithm is over, but we know that it will happen at some point (assuming no negative weight cycles).

So, the crucial observation is that after round $i$, the $i$-th node of the shortest path must have its distance estimate set to the correct value. As the path is at most $|V|-1$ edges long, $|V|-1$ rounds suffices to find this shortest path. If a $|V|$th round still changes something, then something weird is going on: all paths should already be 'settled' to their final values, so we must have the situation that some negative weight cycle exists.