前提

• PC は Outlook でスマホは Gmail を使用
• PC 側でメールを削除
• Gmail 側で検索してもなにも出てこなくなった <- ???

推測

• おそらくメーラーに応じて削除 Box の場所が違うので起きたと思われる
• どちらかでゴミ箱に入れたメールがなくなったと思ったら消した方で確認する必要がありそう