Podrías ver las funciones:
urldecode() a ver que tal te van ..
o rawurldecode()
Lee los comentarios de los usuarios .. hay uno de un tal:
igjav at cesga dot es que usa una funcioncita para ciertos casos que no parece que trabaja correctamente urldecode() (se vé com trabaja con esos códigos que pusistes).
http://www.php.net/urldecode
Un saludo,