Resolvido.
Depois de criptografar a string usando a função AES_ENCRYPT do MySQL, uso a função bin2hex() do PHP para converter esses dados criptografados (que estão em formato binário) em hexadecimal. Em seguida, passo o Hexidecimal como uma string no final da URL. Uma vez que a URL é recebida na outra extremidade, eu uso esta função PHP personalizada para reverter a string Hex de volta para o binário:
function hex2bin($data) {
$len = strlen($data);
return pack("H" . $len, $data);
}
A partir daí, tudo o que resta a fazer é descriptografar os dados usando a função AES_DECRYPT do MySQL e wha-la. A string original foi restaurada com sucesso.