I'm a software developer that worked with connecting websites with payment processors, so I can shed some light on what's happening.
When you enter your CC information to make a payment, the payment processor returns a status of the transaction without giving the vendor any private information. (See testing documentation for Stripe.) There is a set of status related to billing address, which is typically Postal Code mismatch and Address Line # mismatch. It also returns a "fuzziness" rating depending on how far off it is. Say you are on Floor 10 Unit A, you can type this in all sorts of ways ("10A", "10/F, Unit A", "Floor 10, Unit A", "Unit A, Floor 10", etc.)
It is entirely the discretion of the vendor to accept your "payment" regardless of what the payment processor returns. Of course, if the charge is fraudulent, the vendor is out the money.
For your specific online shop, they must've encountered enough fraudulent charges that they no longer want to accept a payment where the billing address doesn't match correctly. Just because other vendors decide to absorb the risk of the transaction doesn't mean they all must. I can assure you that setting up the shop to process the error code specifically for the billing address is non-trivial. It costs them money to do this, but they probably lost even more money from bad payments.
If you pull out your CC bills, using the address of your actual billing address will solve this issue. There's no good reason to not enter this correctly, since the store should allow you to ship to a separate address than the billing address, and they're not supposed to receive your billing address if they're PCI compliant.
If you're really concerned with privacy or whatever, change your Billing Address to a PO Box. The vendor doesn't care about it. They just want the payment processor to say your billing address is correct so that they get paid.
When a CC transaction is deemed fraudulent, it is actually a matter of what is "correct" to determine who takes the loss. If everything is entered correctly, and the product is proven to have shipped to the billing address, then the CC company takes the loss (they go after the card holder, because it is a fully legit transaction). If the billing address is incorrect, then the vendor will take at least part of the loss.
It is actually possible to setup CC processing that doesn't even need the CVC number, but the vendor absorbs 100% of the losses from any reversed charges, so most vendors typically don't want to do this.