A short while ago Ty W posted an interesting question on StackOverflow. Apparently, most graphics software cannot scale images the right way. Usually it's hard to notice the flaw but the linked article does a great job of explaining the problem.
PHP's GD library suffers from the same issue, but Ty discovered that the sample PHP program provided with the article did not work on partially transparent images. After a couple of hours of fiddling I managed to get a working solution.
Apparently, the imagegammacorrect() function in PHP deals badly with images that have an alpha channel. I suspect that it tries to apply the same calculation to the alpha channel that it applies to the red, green and blue channels. To work around this, my solution splits the aplha channel from the original image. The alpha channel is resampled regularly while the red, green and blue channels are resampled using gamma correction.