Yup, I had a similar problem when I ordered an iPhone on CarPhoneWarehouse.com. The order never went through, but I only found out when, after waiting a while, I called CPW who said there was a problem with the card. So I called the bank who gave me much the same reason as you had regarding Microsoft. I cancelled the order in the end.
Commenting is turned off on this blog.