Try getting something like this as this may be a hard problem to track:

I would disconnect 2 of them and see if one turns on and shuts down properly. Add a second and see if it triggers. See if any other couple individual + combo work. I don't know the circuit, but it could be electrical interference on one causing a bit of electrical flow to the other relays potentially. I assume though that might not be enough to drive the relays.

If you are able to turn the machine on/off fast enough in regards to stuck on coils, you can always just bridge the fuse by wire/jumper and make yourself the fuse by manual shutdown. Keeping a solenoid on for an extra 1/2 second isn't going to burn it out. Better than going through tons and tons of fuses. If you keep doing it just touch the coils and validate if they get hot or not.

Again, validate the coils have resistance from above.