Images containing EXIF orientation tag are not rotated on upload
After some mail exchanges with Brad and Andris from Craft CMS, it turned out that there is an edge case where the image rotation on upload will not work if the EXIF extension is not installed (which was our case).

There are two solutions to fix this problem:


Install EXIF extension
Install and use Imagick instead of GD.


As Imagick is the recommended image extension for Craft, we ended up installing Imagick on the server.

This is already working with Imagick on Craft 3, and will soon be working on Craft 2 with the next update (> v2.6.2954).