Steps to reproduce:
1. Get to the center of the map: /tp @p 0 100 0
2. Bring the worldborder in really close: /worldborder set 6
3. Kill yourself a bunch of times. You'll see a lot of times there are valid spawn locations, yet other times it dumps you above/outside the world border, at level 256.
Duplicates MC-64544