Löst.
När jag väl har krypterat strängen med MySQL:s AES_ENCRYPT-funktion, använder jag PHP:s bin2hex()-funktion för att konvertera den krypterade data (som är i binär form) till Hexidecimal. Jag skickar sedan hexadecimalen som en sträng i slutet av URL:en. När URL:en har tagits emot i andra änden använder jag den här anpassade PHP-funktionen för att återställa Hex-strängen tillbaka till binär:
function hex2bin($data) {
$len = strlen($data);
return pack("H" . $len, $data);
}
Därifrån är allt som återstår att göra att dekryptera data med MySQL:s AES_DECRYPT-funktion och wha-la. Den ursprungliga strängen har återställts.