Сам намучился несколько дней с оплатой после покупки консоли, но нашел способ который работает 100% для меня (правда через одно место, как видно ниже). И billing address тут ни при чем (важна только страна).
1. Если добавляли раньше карточки на аккаунт - удаляем все
2. Заходим в консоли в Настройки -> Управление учетной записью -> Данные учетной записи -> Бумажник -> Платежная информация, добавляем карточку
3. Заходим в консоли в Настройки -> Управление учетной записью -> Данные учетной записи -> Бумажник -> Добавить средства, закидываем деньги себе на бумажник
4. Идем в стор и оплачиваем покупку с бумажника
Ниразу не глючило, ниразу не спрашивало 3D secure (???), работает с виртуальными карточками Привата.