SPI Flash Memory with ATMega1284
The underlying problem had nothing to do with software or the chips not working properly. I was using 20cm ribbon cables to connect the ATMega1284 to the external board containing the memory chip. Separating the cables and spreading them a little bit solved the issues. I probably had crosstalk between the signals. The o-scope measurements from the initial post were taken very close to the ATMega1284, where the effect was most probably not visible. To make sure this doesn't happen again in my development setup I shortened the cables to about 4cm. I have not had any further problems so far. 

Thank you all for the time you took to have a look at it! I really appreciate it!