I seem to have got confused by your labelling of the traces.
Assuming:
photo 1: data 0
photo 2: data 1
photo 3: address 0
photo 4: address 1
is the correct ordering,
then the address lines shown seem ok at a quick glance (as you mentioned, digital storage scopes are better this this kind of work). But, there is not much activity on the data lines (doesn't seem to say what the timebase was set to ?).
I would have expected much more activity. With it looking similar to the address line traces. Assuming a big program is loaded up in it and it runs ok.
So maybe it is the overclocking, or there are problems with the Z80 accessing the memory devices.
The garbling, I was talking about, could just be because it was tri-stating the data lines, between access cycles. I mis-read you labels.
As other(s) have said. I would be tempted to check all address, data, control and chip select lines. With the scope and see if any of them look suspicious, while it is running.
It shouldn't take long to do, maybe 5 or 10 seconds per pin.
Anything which is always low, always high or is not at the correct logic high or low voltage levels (difficult to explain quickly, but tri-stating can go between logic levels, need to see control lines at same time, to see if tri-state is legit), is suspicious.
Trying without the overclocking, such as dividing the clock by 2, as suggested above by another poster is a good idea (or a lower crystal freq, as also mentioned).