So since the search form does show up in any other region it means that the module is enabled, there is a
search-block-form.tpl.php somewhere doing it's job. It also means the permissions for the search box are ok.
I went inspecting the navigation menu, within the
<div id='navigation'></div> to see what HTML would be there and there is no HTML to found for the search form there.
The search block is not the only block in the navigation region, there is a main menu block in there as well which shows it's menu links in the navigation region just fine.
The site has a fully customized theme and but with template files. The template files are
html.tpl.php and an empty
template.php file. None of the template files have been modified except for the page.tpl.php where the site logo is hardcoded as
<div id="logo"> <a href="<?php print $front_page; ?>" title="<?php print t('Home'); ?>" rel="home"> <img src="<?php print $base_path.$directory; ?>/css/images/site-logo.png" alt="<?php print t('Home'); ?>" /> </a> </div>