sadly the bank are quite correct and the internet is littered with 100's of like stories where people interpret what they signed upto with Microsoft and what a cancelled debit card really means.
when you pay using a debit card to people like Microsoft or Payday loan lenders you agree to also setup a continuous payment arrangement as there is thus an ongoing relationship.
no CPA's again a card are cancelled should it be lost, damaged, cancelled or replaced, until the recorded exipry date.
the CPA was setup using the details of the card AT THAT TIME.
it a bit like a dca getting a backdoor CCJ at an old address because of your error in not updating your creditors of a move...its YOUR responsibility.
you could argue with MS its unfair, but I've not seen many succeed esp where there are pin no's that should be used and implemented to stop this very issue..again ..that's your responsibility