With the introduction of tags(#) for /locate command in 1.18.2 Pre-Release 1, the command is not locating the nearest structure but gives different results based on which geometrical quadrant you are standing in. This affects both flat and normal worlds.

The following commands were tested:

/locate #minecraft:village

/locate #minecraft:shipwreck

Seeds used

5396388266848481803

-7489398836409264327

Edit: Can also reproduce with /locate minecraft:village_snowy

with seed 

-7489398836409264327