Serial LCD has like a "rolling shutter"
As I noted in a comment to the question  Arduino LCD is displaying gibberish, sometimes,  a PWM's sharp-cornered waveform might introduce a lot of noise into the LCD.  If you have to use PWM, you probably should put a good low-pass filter between PWM and LCD pin 3.

Check whether using a fixed voltage (from a voltage divider or pot) fixes the problem.  That fixed the problem in the case of the linked question.

If you need programmable control of contrast, and can't get PWM to work without heroic measures involving op-amp based filters, you could use a digital pot or a DAC.