El problema de esto es que en realidad lo que se genera y se envía al navegador en las cabeceras del http es un estado de “movido temporalmente” (HTTP/1.x 302 OK) y no un código de error 404 de “página no encontrada”.
Esto pasa porque el header ("location: /error.php?cod=3"); sobrescribe el error 404 que se ha enviado anteriormente.
Por tanto, quiere decir que en realidad no estás enviando el error correctamente. El problema de esto no es por los visitantes del sitio, que van a ver que efectivamente no se ha podido encontrar el contenido que buscaban. El problema es para buscadores, que entenderán que una página que, en realidad no existe, ha sido movida temporalmente a una nueva URL. Así parece que tenemos URLs que en realidad no existen.
La manera de arreglarlo es no hacer la redirección header ("location: …"); después de generar el código de error 404.
Para ello simplemente puedes escribir en la página directamente la descripción del error. Si el código que describe un error lo tienes en otra página, pues simplemente incluye ese fichero con un include de PHP.
header("HTTP/1.0 404 Not Found");
header("Status: 404 Not Found");
include ("error.php");