The backslashes are used up in getting the quotes into the double quoted string in Perl, which leaves no backslashes to protect the quotes in the shell. Try adding another level of backslashes:
system("at 12:00 program.exe \\\"the.server.org:1234\\\"");
Even better, switch to single quotes, and you don't need the extra backslashes after all:
system('at 12:00 program.exe \"the.server.org:1234\"');