when taking a portal from the overworld at coords -5/120/34 I end up in the Nether at or near -3/-3/-2 (The coordinates I'm sent to are just about directly below our actual portal in the Nether which is at -2/52/-2. I easily could have moved a tiny bit from X=-2 and I know I start falling immediately so I expect I'm actually arriving at -2/0/-2.). Upon arriving there's a sky of solid Bedrock above that the player begins falling away from at once, suffocating soon after. If the gamemode is set to Creative the player can punch through the Bedrock and if they fly directly upwards they are in the normal Nether chunk they expected to be at in the first place. In the server console I see the text "<player name> moved too quickly!" and right after the death message for that player is "<player name> fell out of the world."
Seed is -2466281547766755436. This world was created at version 1.9. This problem seems to have started somewhere around 1.9.4, potentially earlier. The only plugin in use on this server is PermissionsEx although the server itself is Spigot.

If I go in the Nether to the coordinates precisely corresponding to the Overworld coordinates of the starting nether portal there's nothing there but solid netherrack. However I do think it's significant that the player arrives at the same X and Z coordinates as their Nether Portal in the Nether but the Y value is far enough down that the player is basically outside of the game world.

This problem is rather severe as it basically renders all our existing Nether portals unusable.

I've tried replacing my Nether files with several backups but the problem persists. It looks like it's a problem with the portals themselves. Please note others are seeing this problem too: https://www.spigotmc.org/threads/nether-portal-bug.156527/#post-1670873