Hi,
I seem to have the same problem on my site
www.fiuh.it (which runs Joomla!1.0.12 + JoomSEF 1.5.0 + JRE SEF Extended + 404 redirect).
The funny thing is that the site used to work until a couple of days ago: when someone wrote a bad url, 404 redirect did its job and started a search or redirected to another page.
Now, yesterday I have upgraded to 1.5.1, then downgraded back to 1.5.0 because of compatibility problems with JRE Sef Extended.
After this, everything works fine on the site, except the fact that the 404 page of JoomSEF is no longer reachable for public users: one has to login to see it. In this way it is useless of course.
Has someone experienced and solved a similar problem? Any ideas?