¿Nos podrias mostrar que pusiste en tu código en 404.php?
Por otro lado lo de penalización es parte del SEO y del tema escasamente se lo que he leido por ahi, sin embargo hasta donde tengo entendido (y si es necesario que me corrijan los que saben) el error se presenta cuando tu al tener una pagina en google indexada ejemplo:
www.mipagina/articulo.php?id=20 al tratar de acceder a ella no se encuentra dicho articulo porque de pronto lo borraste entonces eso genera desconfianza en la pagina y pierde posiciones. En ese caso si aplica usar una manera amigable de decirle al usuario que esa pagina no esta disponible.
Segun entiendo el caso que planteas es mostrar mensajes en caso de ids que no existen aun y que de pronto un usuario metiera manualmente. Yo te aconsejo que en esos casos simplemente creas un condicional donde en caso de no hallar resultados en la búsqueda simplemente le insertas un div con un mensaje donde se indica que no existe ninguna noticia con ese número.
Igual si sabes manejar un poco de apache podrias usar .htaccess para que te haga esa redirección de manera automática.