Another good place would be at the bottom (or top!) of the normal search results screens. I relise it's already on the Not Found page (Not found), but it isn't on the results page (search results).

Thanks,
James Mastros,
Just Another Perl Scribe