I too experienced a problem like this several years ago and spent the better part of 15 hours trying to figure out what was going on.
The machine was a cutting press, which would stroke the head down on to a die. When the machine would cycle the down cylinder would chatter and strike the die several times. I check all of the PLC outputs and inputs to make sure that the signals were not cycling and they were not. I checked all of the power and commons, even to the point of going all the way back to the in coming plant power. When I first got there I asked the maintenance man if any changes had been made to the machine and he said none at all, that it just started going crazy. After 14-1/2 hours the maintenance man asked me if I thought the new relays he installed would have any thing to do with the way the machine is acting? When I asked him what relays, since there were no relays in the panel or on the machine, which I could find, he said the new ones he put in the day before.
Upon further investigation I found that the maintenance man cut an enclosure in the out feed conduit going to all of the outputs. He placed this enclosure under the machine were unless he told you about it you would have never found it. After inspecting the "relays" what I found was that he actually installed mercury relays and that every time the machine would cycle the vibration of the machine would cause the mercury to slosh around and make contact, which was causing the machine to "go crazy".
I am not by any means saying that this is what your problem could be, but make sure that the person who has been working on the machine gives you all of the information of what has been done to the machine. You may also find out that something, which seems so innocent as adding "relays" can turn out to be a real nightmare.
I wish you luck in finding your problem, but if it does turn out to be someone added mercury relays because they thought they were cool, don't worry your not the only one to go down that road and I am sure you won't be the last.