The 2x4 painting requires a 2x5 area, the 3x4 requires 4x5, and the 4x4 requires 5x5. They pop off if one of the uncovered yet required blocks is destroyed; However, if a block is placed after the painting or if a block was in the uncovered area prior to placement it will remain affixed.

I discovered this recreating the layout for the paintings in their texture file in creative mode, desiring to see how my reskinned paintings appeared in-game.

Reproducing this is fairly self-explanatory: Create a wall of the exact dimensions of the painting and spam it until you're bored, then try it on a wall with 1 block added in each dimension. It is worth noting that they can only be placed in the lower left of the expanded area or they still won't appear.

I apologize if this is a duplicate, I searched "painting" on open and in progress bugs and found nothing similar.