Error 404 Not found enviado con PHP me llega como HTTP/1.x 404 OK

Estoy intentando enviar una cabecera de HTTP con PHP de error 404, página no encontrada. Lo hago con el siguiente código:

header("HTTP/1.0 404 Not Found");

Pero estoy viendo que la cabecera del HTTP que se envía en realidad es:

HTTP/1.x 404 OK

Esto tengo entendido que no está bien, porque en realidad está diciendo que OK, como si estuviera bien, cuando en realidad debería decir

HTTP/1.x 404 Not Found

Que especifica claramente que esa página no existe.

¿Qué puedo hacer?