To be honest, I thought a couple of caps would cure the effect but obviously it doesn't
I think you are observing a very subtle effect that happens and causes your system to hang. I think that every time when a state change happens (that occurs not only (but most prominent) at every clock edge) the required current causes a very narrow voltage dip to your CPU and the other components. To avoid this, every one (including me) would tell you: place caps as near as possible to the power pins to stabilize the supply. But this time this doesn't work as it is expected!
Now there are two effects that occur when the voltage drops: first the signals drops, the driving voltage as well, and that would cause the transistors within the chip to act slower and having a higher on state resistance. The latter will reduce the current demands and the voltage drop as well on one hand but also causes the signals to become less accurate. The former will change the signal timing, most likely the delays increase, but not much because due to the reduced supply voltage the switching levels will change as well. And once the switching is over the current requirements will drop so the voltage could recover causing the signals to recover as well.
These somehow weaker and slower changing signals have to travel to other chips. They do not necessarily suffer from that voltage dip, as they themselves didn't switch so far. They may tolerate these weaker signals and as long as the timing margins are sufficient the system still works.
What does an additional capacitor change? It acts as a small accumulator, delivering the charge the CPU is demanding. The voltage should not drop as much, timing and signal quality should not suffer significantly - so far everything should be fine. Now the cap requires its charge back from the supply. This current goes through both supply wires causing a voltage drop there over a lengthy period. And during this time, the CPUs VDD and GND references differ from the remaining system, causing the signal levels to differ as well. I assume this is, what causes the malfunction: your CPU is sometimes (after certain state changes) unable to deliver acceptable signals to the system.
I don't know whether one could proof this "theory". Perhaps this way: you are using again a CPU with capacitor across its pins. You verify that your system is still unstable. +see below+. Then you solder say 3 or 4 additional wires on each leg of the capacitor and stick the other end to the power rails (where a fat 10µ ceramic should be placed as well). This way these multiple connections should be of such low impedance (or inductance) that the voltage drops are getting insignificant.
On the other hand: now that you know your system is working fine without a cap, just go on and use it
It may serve you well this way. And knowing that you are running on the edge may push you enough to consider to switch to a pcb solution, once your hardware evaluations are finished
Good luck so far!
edit(1):
Add another cap parallel to the ceramic one. Use a 10µ electrlytic or tantalum type (pay attention to their polarity!) - these sort of caps do have a higher ESR so they didn't response quick enough but their higher charge may help the temporary voltage drop to become insignificant. Perhaps this alone will cure the situation, otherwise reduce the inductance by adding several wires directly from the caps to the supply rails as said above.