Should the outputs be tested with loads?
Hard to say, but as you have unstable readings without load, the next step is to see whether the readings remain unstable when loaded.
If yes whats the best way to load them.
The obvious load is the rest of the system. Considering your reported symptom, you need to measure the supply rails while the system is working and what happens to them when it shuts down. It could be (maybe, just maybe) that the PSU is shutting down because of overload... in which case the culprit is somewhere else.
If you want to go to the trouble of setting up test loads, filament lamps are a lot cheaper than power resistors. For example: a 5W car bulb (typical interior lighting) will load a 12V supply with about 0.4A (but note that this only applies when the bulb is glowing: when cold, the filament has a much lower resistance so the load on a 5V supply by a 12V 5W bulb is more than the ~0.2A one might guess from 29 ohms at working temperature).
It's best to load both rails not just one.
Would it be worth just replacing all the electrolytic capacitors on both the primary and secondary sides of the board.
That's a hard call. Normally I would say no, because you have no confirmation that any capacitors are faulty, and (more to the point) a "dry" capacitor doesn't really explain why it shuts down.
However, in the absence of any other ideas, you might feel you have nothing to lose... but I think that's clutching at straws in the extreme.