The cleaning of modern and contemporary paintings is a delicate and challenging operation. Many contemporary paintings exhibit rough, clotted and pitted surfaces, where the removal of soil is difficult. Gels are among the most efficient tools to achieve controlled and efficient cleaning of works of art. However, most gels used in the conservation practice are too rigid to adapt rough surfaces, or too mechanically weak to be removed without leaving polymer residues. Several formulations of physically cross-linked poly(vinyl alcohol) (PVA)-based hydrogels, obtained by cast-drying or freeze-thawing of aqueous polymeric solutions, were formulated and characterized. The viscoelastic properties, porosity, and crystallinity of the gels were studied, along with the behavior of water inside the polymeric network. It was shown that the properties of the gels were improved through blending with poly(vinyl pyrrolidone) (PVP). The most promising gel formulation, in terms of mechanical properties and water retentiveness, was assessed for the removal of soil from an alkyd painting mock-up. A traditional gel, gellan gum, was also tested as a reference system. The effectiveness of soil removal was investigated by 2D Fourier transform infrared (FTIR) microscopy, using a Focal Plane Array (FPA) detector. In conclusion, it was shown that the newly developed formulation grants the residue-free removal of soil from rough and irregular artistic surfaces, overcoming the limits of traditional cleaning methods.