Is this something to do with the Bellman optimality constraint itself?
That is part of it, and important for episodic problems without discounting. The Bellman equations link between time steps, providing a direction that data about returns is used to bootstrap value estimates. In episodic problems there are terminal states with 0 value by definition. In the first pass through state space, any state that can transition to a terminal state will be exposed to that fixed knowledge, and could be altered to take that transition. This data is backed up through time steps, at least once per value iteration sweep, and maybe more frequently depending on the order of updating states. You can visualise this effect like a "flood fill" starting from terminal states and filling in the table with true values.
In addition, when there is a discount factor (optional for episodic environments, but required for continuing ones), then this progressively reduces any bias in existing estimates due to the term $r + \gamma v(s')$ repeatedly - over many updates - multiplying any error in the bootstrap from next state by $\gamma$, the discount factor.
For instance, what if a state that in practice had low reward is assigned a very high initial reward value in value iteration? Would the algorithm not construct a value function that highly values trajectories passing through that state?
In limited cases you can construct a combination of environment and starting value function adversarially, so that it does not converge properly. This would require that there is no discounting (or very high $gamma$ and also high $\theta$ cutoff to stop iterations early), and a set of self-consistent high start value estimates that form a loop preventing the iterations from making changes. Any single "rogue" high value estimate should quickly get reduced by the update mechanism (only exception would be a high value state that can loop to itself deterministically and without any discounting applied).
In this question, the OP constructs just such an adversarial start condition: Is the initialisation of $V(s)$ and $\pi(s)$ really arbitrary in policy iteration?
So in some senses, the initialisation is not strictly arbitrary, in that you can set up non-working examples. However, the value iteration algorithm is far more robust than your initial concerns imply, thanks to the effects described above. In addition, if you are implementing a solver then you get to choose initialisation, and can make conservative choices (e.g. don't initialise any value higher than max possible reward - there is no known benefit to doing so for dynamic programming algorithms). These choices are not strictly required, the space of working initialisations is much larger, but you are also not required to attempt to code truly arbitrary value table initialisation.