Relates to MCPE-45526? Only tested on shipwrecks and villages but may affect more structures.

Steps to reproduce

_{Updated for 1.18}

Shipwrecks

1. Create a world with the seed 668 (thanks MCPE-119822)
2. /tp 280 60 5 and you should see a shipwreck close by
3. /locate shipwreck
   → The nearest Shipwreck is at block 280, (y?), 24
4. /tp 280 60 -5
5. /locate shipwreck
   → The nearest Shipwreck is at block 232, (y?), -280 (several hundred blocks away)

Villages (same seed)

1. /tp -272 64 550
2. /locate village
   → The nearest Village is at block -280, (y?), 680 (~130 blocks away)
3. /tp -272 64 540
4. /locate village
   → The nearest Village is at block -264, (y?), 184 (~350 blocks away)