This isn't true. You can't intentionally use paint or wallpaper that blocks signals in public spaces or places where a wireless device is expected to be able to be used(like a movie theatre) in the case of an emergency.

In the eyes of the FCC it is no different if it is willful.

I don't think so. The FCC law in question, from my reading, specifically mentions malicious interference, but says nothing about building materials.

Nobody has ever been prosecuted for their choice of paint on their private property.

There is indeed a distinction between your own private property and a business that invites the general public in to do business. The cinema is still private property, but it's still also public space.

That said, I don't think anyone has ever attempted a ruling on whether chicken wire/Faraday cage in the walls of public spaces is permissible according to the FCC. I'd doubt such an attempt would make it far; there are so many buildings made with metal siding which do a fantastic job of reducing cellular signals to useless levels.

I can't find anything to back this up, but I remember that in the 90ties is was well know (incorrectly or not) that you needed a permission for this.

I don't have any citations but it seems unlikely given that there's certainly no law that requires building structures to not block cell service. (I've been in enough buildings that seem to pretty much act as Faraday cages.) Intent matters I suppose but seems pretty unenforceable.