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 ...
You'll need to contact your hosting provider. There are any number of ways that this "PHP switching" can be implemented, but typically each major PHP version has its own separate modules/config files that tell it which modules to use.
So the fact that ImageMagick is installed on the server doesn't mean that it's globally available to every PHP version that'...
Click on the "i" graphic and it will probably tell you that GD is installed, but Imagick isn't and it is recommended.
You can verify that Imagick is installed and available to PHP/Craft by going to yoursite.com/admin/utils/phpinfo and searching for "imagick". If it's not there, then it has not been installed properly.