Zu Deinem Layout - 2-lagig mit Massefläche auf der Bestückungsseite:
Durch die horizontal verlaufenden Leiterbahnen kommt es zu undefiniert langen Wegen vom VCC-Pin zum Masse-Pin. Das gilt ganz besonders für die speicher-Chips und den Prozessor. Hier wäre es günstiger gewesen, die Massefläche auf die Lötseite zu legen. Das dürfte vermutlich der Hauptverursache für die Betriebsprobleme sein. Es ist generell keine gute Idee, das Layout NICHT mit dem Verlegen der VCC und GND Leitungen zu beginnen. Wenn der 10uF so deutlich erkennbare Auswirkungen zum Besseren zeigt, deutet das auf eine zu hochohmige Versorgungszuführung vo Netzteil hin. Der 10uF puffert die durch die Schaltvorgänge erzeugten 'langsamen' Stromsptzen und glättet somit VCC. Das müßte eigentlich mit dem Scope auch deutlich zu sehen sein. Deine Feststellung "Also liegt es tatsächlich an der Spannungsversorgung" ist wohl zutreffend. Kontrolliere aber trotzdem, ob nicht immer noch Spannungseinbrüche auf VCC auftreten, die gößer wie 0.3V sind (den 10uF ev. erhöhen auf z.B. 47uF parallel 100nF). Versuch mal auf der jetzigen Leiterplatte das GND-Ende eines jeden 100nF Stütz-C's mit einem Draht (0.5mm Durchmesser) direkt zum GND-Pin des IC's zu verbinden. Das sollte die Stützwirkung weiter verbessern, da der GND-Pfad des Stütz-C's kürzer und definierter wird. Du kannst auch versuchen, einen zusätzlichen bedrahteten 100nF zwischen VCC und GND Pin zu löten (besonders bei den RAM-Chips). Erhöhe doch auch mal die +5V auf +5.2V. Das liegt noch in der Spec. Verbessert sich dadurch ev. der Betrieb, wenn ja, sind immer noch zu viele Störungen auf der VCC.
4-lagen PCB:
Generell wie schon angeklungen die beste Lösung, da so die Impedanz der Versorgung für steile Stromspitzen am geringsten ist. Die so gebildete Kapazität des Plattenkondensators ist jedoch nicht sehr groß, die notwendigen 100nF Stütz-C's ersetzt das auf keinen Fall. Ich erinnere da mal an die 500pF Drehkos in den alten Röhrenradios. In der Größenordnung dürfte sich der erzielte Wert bewegen (wenn überhaupt).
Testbetrieb:
Laß die CPU in einer Schleife immer auf die selbe Adresse die selben Daten schreiben/lesen. Das erzeugt eine quasi-statischen Betrieb und Fehler/Störungen lassen sich leichter untersuchen und zuordnen. In Deinen Logiganalyzer-Plots ist viel zu viel auf einmal zu sehen. Teste auch, ob alles ok ist, wenn sich viel Bits auf einmal von '1' auf '0' und umgekehrt ändern. Diese Situationen erzeugen starke Stromspitzen auf der Versorgung. Auch dann muß alles stabil funktionieren. Derartigen Fälle können zu später schwer auffindbaren Fehlern führen.