Time to pop the cover off the controller box and start the google hunt I'm afraid.
The scope of possible problems is large:
PC setup
Parallel port setup
Windows setup
Software other than Mach running on the PC including virus checkers.
In slightly older PCs even the chipset on the motherboard has been known to cause problems, eg the CPU is fast enough but the motherboard imposes large and/or variable interrupt latencies.
CPU speed.
Insufficient RAM causing Windows to occasionally, or frequently access the hard disk.
Wiring problems: shorts, breaks or sometimes just incorrectly connected at the controller.
Controller problems: This guy added a buffer
http://www.homediystuff.com/fixing-a-chinese-made-cnc-stepper-motor-driver-board-tb6560-chips/ , others I seen needed to add resistors somewhere (I wasn't paying attention) and quite a list of other "fixes".
Power supply problems, as snoopy points out. A common problem could also be PC, Mach, interface cable or controller based.
I would not despair yet, many people have had many issues so there is a lot of information out there. Reading it will take some time.