Paintings seem to need a 1-block border around them to be placed if they're larger than 2x2. If the border isn't present, the larger paintings won't generate. If the border is broken, large paintings will fall off the wall.

For example, if x is painting on a block, y is a block, and z is air:

This is not allowed:
z z z z z z
z x x x x z
z x x x x z
z x x x x z
z x x x x z
z z z z z z

And this is not allowed::
z y y y y z
y x x x x y
y x x x x y
y x x x x y
y x x x x y
z y y y y z

But this is allowed:
y y y y y y
y x x x x y
y x x x x y
y x x x x y
y x x x x y
y y y y y y