You can evaluate a templated adp file for 404s with the following. This will properly return a 404 error code.
In config.tcl:
ns_section ns/server/${server}/redirects
ns_param 404 "global/file-not-found.adp"
Create your templated adp page called 404.adp:
<master>
<h2>Sorry, that page cannot be found.</h2>
In file-not-found.adp:
<%
set rendered_page [ad_parse_template "/www/global/404"]
ns_return 404 text/html $rendered_page
%>