First some background:

We have a Windows XP application which we distribute from our
Unix/Linux (I don't recall which flavor) server. In the binary .exe
file, we have two "placeholder" constants which are replaced with a
unique download code and tracking code whenever the file is
downloaded.

This is done by reading the file in Perl (using binmode) and then
using a "$line =~ s/PLACEHOLDER/$value/;" command to insert the unique
value in place of the placeholder.

Now we would like to "sign" the binary file before sending it out, but
after embedding the download and tracking codes. (If we sign the file
with the placeholders, and then embed our unique data in place of
those placeholders, that changes the value of the signing hash,
leading to a security warning on the client machine.)

So the question is this -- HOW can we sign a Windows binary .exe file
in a Unix/Linux environment? Is there some flavor of "signfile.exe"
out there for Unix/Linux machines?

You can do this by installing Mono on the linux box, then using it's
signcode utility (which is nearly identical to the windows
command-line version: signcode.exe)