Search box doesn't work if on 404 page

If you get a page not found (e.g. http://drupal.org/foo) and try using the search box you just get another page not found ...