DC voltage shift with AC conditions is a classic bipolar amplifier rectification effect. TL431 is a bipolar amplifier, and susceptible to this effect, as are many others.
While TL431 is marketed as an "adjustable zener", it's anything but; an accurate description is a self-powered open-collector op-amp with a massive but suspiciously stable 2.50V input offset voltage. This makes it much more useful than as a shunt regulator; as seen here, it serves well as an error amplifier for isolated feedback. And, as a not-zener, we can expect to see very different behavior for frequencies above fT; terminal impedance goes up, and eventually, rectification effects occur. (Typically, from ~10MHz to 100s of MHz would be relevant for this effect. Or beyond; I've seen plenty of audio equipment that detected the distinctive beeping and clicking sounds that accidentally come from nearby cell phones.)
Presumably, removing the capacitors is increasing EMI around the regulator, shifting its offset. RF is rectified to a DC offset, increasing the feedback signal and thus decreasing the output voltage.
Probably. Maybe something like that. Is that the correct rectification direction? I forget if I've had a chance to measure that before, actually. In any case -- it's likely to shift somehow; whether up or down, depends on the device.
A good solution (besides fixing the underlying EMI problem itself..) is a small cap between REF and ANODE (or, functionally speaking: -IN and VEE/+IN). This reduces loop phase margin, so not much can be used; typically 100-470 pF is adequate.
As for how the EMI is getting to the regulator in the first place -- who knows. Perhaps it's proximity, the regulator might be near some metal or other traces that have CM noise between them [the regulator and the conductors]. Perhaps it's poor layout (no ground plane?). It's unlikely to be supply ripple (differential mode), given the comparatively low impedance (large capacitors, extra filtering) there. (By extension, using two 'Y' caps here is probably immaterial; one likely will do, or it doesn't matter which rail the two connect to, Vo- or Vo+.)
Also, just to clarify for readers (you probably know this already): it's not material whether EARTH is actually earthed; RF of course doesn't know or care what's at the end of a dozen meter cable (at least, for certain bands of RF). The 'Y' caps serve to close the loop between input (mains) and output, serving as the shunt capacitors in a common-mode low-pass filter, to absorb noise generated by the supply (particularly the isolation transformer, which spans the common-mode path). Typically chassis connections are provided (if not a whole enclosure or partial frame, then screw holes in the PCB), which may serve as the reference plane ("earth" for RF purposes), and so 'Y' caps are often tied to it.
