From a functional perspective it is a search.
When you search for something you expect either search results or your search didn't return any hits. None of those cases call for a 404 page. When that happens all people will raise bugs.
See how you searched for a tag:
I do admit that the page could do with a message that no results match the search criteria, something like that is however present in the new navigation on Stack Overflow:
tl;dr; That is not as bug and certainly doesn't need to do a 404. The particular search state could use some love, maybe backport the new navigation design.