【ページング】URLが／（スラッシュ）ではページが404になる

ページングをすると４０４になることについてはいろいろな記事として挙がっていますが、
調べても解決できなかったため、質問させていただきます。

条件として、記事タイトルとカスタムフィールドをマージさせて
1つの入力フィールドで検索させるようなカスタムをしつつ、
カテゴリの情報をたして以下のように検索

$paged = get_query_var( 'paged', 1 );
parse_str( $query_string, $args );
$args = array(
    'post_type'   => 'post',
    'post_status' => 'publish',
    'post__in'    => $post_ids,
    'cat' => (string)htmlspecialchars(addslashes($_GET["cat"]),ENT_QUOTES),
    'paged'=>$paged
);
query_posts( $args );

した場合、
http://www.hoge.com?pages2&=hoge&cat=0
ではページ遷移するのですが、
http://www.hoge.com/page/2?s=hoge&cat=0
では404になってしまうようです。

また、キーワードが空の場合
http://www.hoge.com/page/2?s=&cat=0
は、いずれの場合も遷移できることも確認しています。

調べた限りで、表示件数（posts_per_page）の制御なども試してみましたが、
改善しないようでした。

最悪は検索時はパラメータで遷移させるようにすればいいのですが、
解決策を御存知な方がいらっしゃいましたら是非ご教示くださいませ。