It sounds to me like either a timing problem or else interference.
I had similar problems with my setup, and I believe my situation was a result of engine noise interfering with the data. I added buffer chips on both ends of my interface and it seemed to eliminate 99% of the problem. Sometimes I would still get a weird fluke where the screen would turn into garbage at random points.
You may want to try adding pull-up resistors on the LCD's data lines, and capacitor(s) on the power leads.
Also, if you run a parallel cable long distances, this can sometimes cause problems, like in my situation.
Another issue is timing. Sending raw data out the parallel port under Windows is a nightmare in terms of timing. If you take a logic probe and monitor the clock line on the LCD (for clocking in characters), you will see what appears to be random pulses. Sometimes when the system gets busy, the timing requirements for the LCD may not get met, and, for instance, data that was meant for an LCD control code might instead get sent to the display, etc.
Have you tried using a different LCD module with the same controller chips on it? Sometimes this helps too.