I wonder how this became a problem. Your CC number is not just 16 digits long. It's 16, plus expiration, plus the 3-4 extra security digits, plus your name, plus your zip code. That's quite a lot of entropy.
Billing address verification is extensively used in the UK.