My expectation was that the EXPR would be evaluated once and the invariant result used between every element of the LIST.

The EXPR is only evaluated once, before join is even called.

$ perl -MO=Concise,-exec -e'join($s, $x, $y, $z)'
1  <0> enter
2  <;> nextstate(main 1 -e:1) v:{
3  <0> pushmark s
4  <#> gvsv[*s] s
5  <#> gvsv[*x] s
6  <#> gvsv[*y] s
7  <#> gvsv[*z] s
8  <@> join[t5] vK/2
9  <@> leave[1 ref] vKP/REFC
-e syntax OK
[download]

The result is a scalar, and scalars aren't invariant as you yourself demonstrated.

Is the behaviour of join with a tied scalar prior to 5.18.2 correct but not clearly explained in the documentation or is it a bug that has now been fixed?

The old behaviour is correct. The new behaviour is even more correct. The change was intentional.

The documentation says Joins the separate strings of LIST into a single string with fields separated by the value of EXPR, and returns that new string and the wording looks the be the same for for all versions

That's an accurate description of all versions of join.