お早い修正ありがとうございます。
確認できました。
> よくわからなかったのは(こちらで別テーマで試した限りですが)「?s=a&cat=100000」だと「ページが見つかりません」になるのに…
全くの無プラグイン状態で別のテーマとTwenty(公式デフォルトテーマ系)などで確認した所、
全て検索条件に対する記事が無い形で表示されているので、該当のような状況にはならなかったです。
ただ、制作メンバーに聞いたところでは、「可能性として考えられるのはマルチバイト文字を弄るプラグインとか、入力フィルター系のプラグインで文字列操作をしているとか?」と言う回答を得れました。
何故そのように起こるのか自体は、再現も出来ていないのでまた解れば別で報告しますね。