Going through the Nether Portal freezes the Client

If I go through the nether portal, my client shows the brown background pattern and freezes. Gamemode has no effect. If I kill the client process and reconnect, I am trapped in the netherrack at a seemingly random coordinate (not: division by eight rule, also not the same coordinate as overworld).
There is no stacktrace to be found in the log.
The problem has been persisting since at least 1.9-pre4