It's not the bank that's blocking me, it's the merchant. Since merchants are the ones on the hook for card-not-present fraud, they refuse to ship items anywhere but the address registered with the credit card.

I don't know which debit cards you're referring to but I'm almost 100% sure that the cardholders are not liable for fraud. Meaning someone else along the chain is liable and is monitoring/blocking transactions to reduce that liability.