"Weirdly when I did the same for a replacement 74LS04 the board seemed to get worse".
It maybe you've got a 'fake' 74LS04. This means, it may be marked 74LS04, but it's really a 74HC04 or a 74HCT04. I had this situation also already. The problem is, the functionality is the same - but levels, delay time, etc. are different. There may be situations you won't even recognize it's not the chip you're expecting it is, but in other situations (especially, if the device is used 'out of spec') this will prevent correct functioning of the circuit. Sometimes you have to use a replacement of the same manufacturer for repair if the specs haven't been followed when designed. These are no good designs, but the only way to bring such a design back to life is to use exactely the same chip that was used originally. Some chips of the same type from different manufacturers are interchangeable when used wihin the specs, but they may behave different when exceeding spec limits. An example is using digital logic ICs in an analogue way. Especially when using CMOS 40xx logic some engineers used to realize a delay time inserting a resistor in series to the output of one gate and a capacitor in parallel to the input of another gate. This results in a delayed signal indeed - but how much the delay is depends on the switching levels of the input of the second gate. So using the same IC type form another manufacturer may change the delay time.