The Craft CMS instance where I noticed this is running version 2.6, but I updated it last month from version 2.2.
While we did not notice any problem, according to the client, they were able to upload pictures taken with their smartphone and Craft would rotate the images correctly before the update.
As far as I can tell, Imagick is not available on this server (I checked PHPInfo) so GD has always been used. I also made sure that the "rotateImagesOnuploadByExifData" setting is set to true by adding it explicitly to the general config.
Any idea what could be causing the issue and would installing Imagick solve the problem?