the ALL Category would be a static menu item not created from the database.
in the menu, you would create the static All category menu item and leave the URL variable blank in the link, for example:
results.php?Category=&Search=Search
then you would add the dynamic menu after it.