Hi Joe,
To my surprise, if I use a skin that exposes the search input rather than a link it seems to work on my local machine.
However, in general, I would not have expected it to work and would avoid trying to get too fancy with the 404 page because it isn't used like other pages. We don't redirect to it, we make a server side web request for it just so we can scrape the html from it, which we then render in the browser while still returning the 404 status code. I would not want to create circumstances that encourage the user to then make a postback against the 404 page. Best if they click a link and go elsewhere like the site map, or the google search is done with javascript requests back to google, so it doesn't post back to the 404 page.
Best,
Joe