Steps to reproduce (pak64 120.4.1 r1974):
New Game -> Map number: 0 (with default Landscape/New Game Settings) -> Start Game
Map number 0 only has Mediterranean climate and below, but there's bound to be a Coal mine or Coal power station somewhere even though their allowed climates are Temperate and above.
This is probably a feature and not a bug. Unfortunately, there seems to be no way to close this bug report. :-[
Indeed, in order to avoid broken industry chains after the place search exhausted all possible locations, a last attempt is done ignoring climates.