Okay, I am a bit confused now.
While I was waiting for response for the warranty, I was experimenting further. I almost did everything: BIOS update, looked for a VGA BIOS update (which I did not found), tried to reproduce the problem on Windows (which did not work) and last but not least I once again stumbled over the "If you have a stability problem, read this first" sticky.
Then I tried all options suggested in this thread - at least all, that applied to my configuration.
When I tried
I tried once again... and the PC did not crash. So I made the SAME test as shown in the video. I toggled Fullscreen for 87 times - then my finger began to hurt - but the PC did NOT restart anymore.
Now I am ashamed not to try this earlier, but I really do not understand why this helped. It still does not explain why my PSU sometimes fails to re-power up after a crash... and maybe this is a defect in the PSU... but... (sorry for the expression) WHAT THE FUNK?
I will continue testing ... see if I can get it to crash once again.
At least I have to rewire all my Hardware. Maybe this will drive the PSU nuts again...
EDIT: Every little piece of Hardware is connected agaon and all external devices as well. Video still causes no crashes...