Thank you. Some of the machines indeed had a different version of the Encode module. There are still some, though, that have the same version, but produce different results. The only difference I can see is one of them is 32 bit, while the second one is 64 bit (but Perl is 32 bit).
Update: I ran the process via strace on both machines. One of the many differences I noticed was the size of the read buffer: on the 32 bit machine, read(3 is called with the buffer size of 32768, while on the 64 machine, the size is 65536. There might be a problem if a multibyte character is split between two subsequent buffers. It would also explain why the output is not different when the input is processed line by line (no line is longer than 32768 bytes). It still doesn't explain why substitution fixes the problem, though.