Is_search not working on search results page

I have an extra submenu with this code in the sidebar:

if(is_404() || is_search()) :
    echo 'should be empty';
else :
    if($post->post_parent == '68')
        $children = wp_list_pages("title_li=&child_of=".$post->post_parent."&echo=0");
    else
        $children = wp_list_pages("title_li=&child_of=".$post->ID."&echo=0");
    if ($children) { 
        ?><ul><?php echo $children; ?></ul><?php 
    }
endif;

I have a problem with the first line. It’s working fine on the 404 page and on the search page if you search for something that doesn’t exist, but when you look for something that does exist, the submenu is popping up in the sidebar. What is wrong with this code?

If what you want is for the else to show up on 404 pages and on search pages but only when the search returns no results, the conditional you need is …

if(is_404() || (is_search() && 0 === $wp_query->found_posts)) {
  // ...
} else {
  // ...
}

The difference between that and your code is that I added an additional check to see if the search query has any results. The brackets around is_search() && 0 === $wp_query->found_posts) make the || operate against the whole clause, just like brackets in math, really.

If you don’t want the else on any search or 404 pages then you need…

if(!is_404() || !is_search()) {
  // ...
} else {
  // ...
}

… but that is what you have so I am unsure what you are trying to achieve.