I think the added complexity here is that while you are using a Steam version of the game, and you are paying with Steam funds, the Marketplace is always run by Microsoft so, Microsoft might have been able to see the purchase failed, but they couldn't verify the state of your Steam wallet, which I'm sure Steam doesn't share with anybody.
Maybe, you can try Microsoft for a refund, see what they say.