Couple of options:
1. Edit the existing Header Element under Appearance > Elements and under Background Image you can set a fall back image. This will be used when no featured image is available.
2. If you want to have different images, one for Search and one for Archives then you would need to create new Header Elements for each. There are Display Rules for Search Results and All Archives. If you use this method you will need to Exclude those display rules from the original Header Element
Note: If you use the Duplicate Post plugin, then you can create new drafts of the existing Header Elements.