Normally, I wouldn't have noticed such a thing, but it was hosted over a DSL connection so large images would load visibly slow.
Knowing that the code worked fine on our development environment, it seemed it had to be something with the server. After checking permissions on all the folders where generated images go, I started going through the code to generate images. Even though the "Regenerate Thumbnails" extension said everything worked, I had my doubts.
As it turned out, my doubts were well founded. We needed to install php-gd on the server to make it work. Now, when it is supposed to use a thumbnail, it uses a thumbnail.
Sometimes it's the simple things that make me smile at the end of the day.