I don't really belive that they are totally anonymous because somehow - as you wrote - they should send you that card. They register that name and address somewhere in their database. I know you can tell that e.g. you have ordered it for one of your friends but I don't know if they will belive you or not...
My opinion is that nothing is anonymous anymore in connection with debit/credit cards (bitcoin or not) but they advertise their card with the anonymity to be able to use much higher fees.... but this is only my opinion

there is no point in using bitcoin debit cards if you are looking for anonymity and a "fiat" card where you can spend everywhere since you are not spending bitcoin but converting to fiat then spending it using these cards. just buy prepaid cards from shops where you simply can pay cash and be nearly 100% anonymous when doing that.
if you want anonymity then use bitcoin directly and if you want full anonymity then use an anon coin like Monero.

ps. regarding address how about using a P.O. box?

As long as the P.O. box is not yours
Anonimity matters only if someone really wants to find you (even the tax authority). In that case they can ask the P.O. box service provider (e.g. the national Post) to give them your details, because you need to sign something to have a P.O. box...

Not very anonymous since they'll have information about your usage and may collect other data (address, IP, etc), but considering how shady some of these companies are, it's probably a good thing for them not to have your ID even if they have quite a lot of information.

Cards are definitely not intended to be an anonymous payment system, so since in the majority of circumstances you'll have the option to use cash, you might as well just do that (or indeed, actually spend Bitcoin rather than fiat from one of these cards).

I also think that these anonymous Bitcoin debit card services are hanging by a thread and at any point they could become illegal, so I personally steer clear.  I did have a verified Xapo card once though.

Usage is not a big thing if you buy in shops or withdraw money from various banks. The real IP address can be concealed.
I think except the address the card is sent to, there are the same amount of information revealed as you would buy with Bitcoin.