Also remember that buffering plays a part in exactly when a message appears. Setting $|=1 will make STDOUT unbuffered, and might alter the order: as it may if you print to STDERR instead.
Unless the OP has done something we can't see, STDOUT is line-buffered by default, in which case buffering doesn't matter here at all and is not the issue.