当たり前の話なのですが、小規模な個人商店などと違って Microsoft は毎日膨大な請求処理をしているので、「あなたに請求しました」という情報は(請求書そのものですから)見つけられても、「Microsoft はあなたにこれこれの請求はしていません」という情報を確実に確認するのは困難でしょう。なので「Microsoft に問い合わせても何も得られない可能性が大きい」と書きました。
カード会社としては利用者側の身勝手な行動でたびたび支払いを止められてはかなわないので請求元への確認を求める手順になっているのかもしれませんが、できないものはできないので強く主張して止めさせるしかなかったでしょう。