Is_search not working on search results page

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.