Okay, I have finally sussed this problem on both Windows and Linux.

The following code is written in Perl but it can be quite easily adapted to work for pretty much any programming language.

Procedure for escaping an arbitrary argument for use at a command line

sub escape_arg {
	my $arg = shift;

	# Windows cmd.exe:
	if($^O eq "MSWin32") {

		# Sequence of backslashes followed by a double quote:
		# double up all the backslashes and escape the double quote
		$arg =~ s/(\\*)"/$1$1\\"/g;
		
		# Sequence of backslashes followed by the end of the string
		# (which will become a double quote later):
		# double up all the backslashes
		$arg =~ s/(\\*)$/$1$1/;

		# All other backslashes occur literally

		# Quote the whole thing:
		$arg = "\"".$arg."\"";

		# Escape shell metacharacters:
		$arg =~ s/([()%!^"<>&|;, ])/\^$1/g;
	}

	# Unix shells:
	else {
		# Backslash-escape any hairy characters:
		$arg =~ s/([^a-zA-Z0-9_])/\\$1/g;
	}

	return $arg;
}

Procedure for escaping the name of an arbitrary program for use at a command line

That is, the 0th argument of the call. On Windows, this needs different treatment from the actual arguments.

sub escape_prog {
	my $prog = shift;

	# Windows cmd.exe: needs special treatment
	if($^O eq "MSWin32") {
		# Escape shell metacharacters
		$prog =~ s/([()%!^"<>&|;, ])/\^$1/g;
	}
	
	# Unix shells: same procedure as for arguments
	else {
		$prog = escape_arg($prog);
	}

	return $prog;
}

Procedure for escaping an arbitrary command

As presented in the form of a program followed by a series of arguments for that program. Returns a string.

sub escape_cmd {
	die "No call supplied\n" unless scalar @_ > 0;

	my @escaped = ();

	push @escaped, escape_prog($_[0]);
	push @escaped, map { escape_arg($_) } @_[ 1 .. $#_ ];

	return join " ", @escaped;
}

Tests

These subroutines worked on my Windows machine and the Linux machine which hosts this site. If you find faults or want to suggest some more test strings, be my guest.

The complete list of strings I used for unit tests is:

yes
no
child.exe
argument 1
Hello, world
Hello"world
\some\path with\spaces
C:\Program Files\
she said, "you had me at hello"
arg;,ument"2
\some\directory with\spaces\
"
\
\\
\\\
\\\\
\\\\\
"\
"\T
"\\T
!1
!A
"!\/'"
"Jeff's!"
$PATH
%PATH%
&
<>|&^
()%!^"<>&|
>\\.\nul
malicious argument"&whoami
*@$$A$@#?-_