Done whole procedure.
Tested with a third combination and page: No Problem.
Re-created every element (jpg, block, header, layout) of the second combination which didn´t work – and it doesn´t work.
Changed the “Layout key (unique identifier)” (yes, it really is/was unique) to have difference to the former layout. It works!
May be former layout with other elements existed, which results in another page header. I guess a new layout with the same (and therefore still unique) key obviously refers to deleted elements, so a deleted page header has been shown – or a fallback to default happend in cause of inconsistend referrers.
Conclusion:
1.) Deletion means deletion and your theme does not handle the keys properly.
2.) If deleted keys still exist in the background, at least a check of the key should happen when adding new elements. As there isn´t any “trashcan” for elements, rather 1.) would make sense.