That was it! When I test the search from the nav bar and use the enter key to submit the form it will not include the search parameter in the URL.
To fix this you will need to go into the Templates > Main.dwt.php file. Go into split view and select the submit button in the nav bar. In the code you will need to update this submit button to look like this:
<input name="Search2" type="submit" value="Search" id="Search" alt="Search" />
Then you need to add in a hidden form element to this form, it can be before this submit button or just after it, here is the hidden form element you will need to add:
<input type="hidden" name="Search" value="Search" />
This is a problem in IE, if you use the enter key to submit a form it will not always submit what is in the value attribute of the submit button. Changing the name of the submit button to be search2 then adding a new hidden form element with the name search and a value of search will fix this.
If you encounter this problem in the future this is a pretty good workaround for it. I will make sure that a bug is logged for this issue. Thanks for being so patient and working this out with me.