I think you have almost got it all working, there is only one little thing that I can see that should be updated.
In your code that looks like this:
<li><a href="<?php echo($assumedRoot); ?>Products_Results.php?Search_x=true&CategoryID=<? php echo $row_menuwriter_productcategories["CategoryID"]; ?>"><?php echo $row_menuwriter_productcategories["CategoryName"]; ?></a></li>
You should update the Search_x to just be Search like this:
<li><a href="<?php echo($assumedRoot); ?>Products_Results.php?Search=true&CategoryID=<? php echo $row_menuwriter_productcategories["CategoryID"]; ?>"><?php echo $row_menuwriter_productcategories["CategoryName"]; ?></a></li>
I did some testing on your live site to confirm that this is the way it should be. I must have been testing this from your search page the first time to get that value, sorry about that. Please update this and let us know if there is any other problems.