Same problem here, tried 2 credit cards (US and AUS), tried paypal, payclick, entered an endless loop of re-verification and decline.
Shoot 2 furious emails to apple support, honestly I think their database has serious problem.
I cannot believe they are so ignorance, this problem started to happen 1 year ago and still no solution, they just don't care.
Next time don't laugh at Microsoft.