Active signal blocking / jamming with electrical devices are illegal in the US, but passive devices like signal-blocking wallpaper and windows are entirely legal.

Not necessarily. Loads of buildings are faraday cages by accident. I know my old school gym completely blocked cell signal due to how it was built

Many big-box stores effectively block most if not all cell signal; you might not notice because Home Depot provides free wifi.

I assume it's unintentional though right?

I suspect so, but I wouldn't put it past Costco to intentionally block most of price checking say ...

(Costco being the only one I've been in that didn't provide store-wide free wifi.)

What kind of law would prohibit you to block out cell signal in your own building?

An entirely sensible one which prohibits you from preventing an emergency call being made in case of fire, injury, crime etc.

> which prohibits you from preventing an emergency call being made

The solution to this is simple: A land line behind the counter.