In the first one it looks like it's the wrong phase (rising edge triggered) maybe, plus a little delay somewhere, somehow. The second one is delayed erroneously, somehow.
I forget if -- and which AVRs, if it varies -- the slave SPI is externally clocked, or if SCK is taken in and re-synchronized to peripheral clock and then processed as any other internal signal. That might be something to look for. So if their peripheral clocks aren't synchronized, as they drift in and out of phase, you'll see errors come and go. Or if they're clocked at very different rates, they'll come and go frequently, perhaps multiple times within a given frame, but also perhaps sometimes none and sometimes many.
If nothing else, you could add a D flip-flop and reclock MISO to SCK (possibly with an inverter, if needed to align it to the correct edge), and advance the edge timing on both sides accordingly; but this shouldn't at all be necessary.
If one or the other is reclocking internally, you'll basically have to deal with that as it is, either by using a lower clock rate, external reclocking, or changing to a chip that isn't so dumb.
Tim