Al final era un error en el str_replace().
Reescribí el código entero a mano y lo comparé con el que tenía, que es el método que uso para ver si he cometido algún error estúpido de sintaxis.
El script que puse al inicio funciona siempre y cuando disfracemos la url del archivo de la siguiente manera:
Código PHP:
$url = str_replace("//", "/", $url);
$url = str_replace("http:/", "http://", $url);
$url = str_replace("http://dominio.com/", "/homepages/16/d312312366/htdocs/", $url);
Y luego ya sí podemos hacer el unlink.
Muchas gracias Alzuwaga por tu tiempo.