I managed to identify the problem: Apparently, one of the developers in our team sometimes manages to change the default location property of folders when adding them to StarTeam. So instead of checking in files with a location relative to the project root, we end up with an absolute path in our repository.
I was able to verify this by deleting the file in the original location (i.e. NOT in the Jenkins jobs folder) and then watch as the files reappeared in their original location during the Jenkins checkout. What really lead me to investigate this further was to try an checkout the files from StarTeam using a cmd-line utility to check the files into a different location. When this still didn't get all the files checked out I assumed that Jenkins was no longer to blame but instead something else was wrong.
The reason I hadn't noticed this before is partly due to my little experience with StarTeam and due to all of the developers in our team using the same mappings and paths in our development environment. Hence, the absolute path placed the file in the right location on all machines because the paths used were identical.