No entiendo bien el problema, si la página no existe, el propio apache te va a generar un estatus 404
Esto por ejemplo, produce un 404
http://www.masteatro.com/cartelerate...lara-madrid222
esto
http://www.masteatro.com/cartelerateatro/404.php
Obviamente no, porque esa página si existe, a su vez tu 404.php debe de tener algun include, porque en el primer caso no muestra todo el header con los estilos, favicon y demás.
Creo que todo pasa porque en .htaccess tenes puesto
cuando deberías tener
es decir indicando que 404.php está en la raiz, y para el header usar un include con la url completa para evitar problemas
Saludos