Shortcode not working on not found page

extremely late here, but the 404 page usually not a page to which you can assign content and therefor no shortcode support. If you can edit the template then you can use the do_shortcode function to add it, but you might as well call the wordpress search form function itself.