@Yilmaz,
Think I found it after reading these:
https://stackoverflow.com/questions/76424572/nucleo-board-needs-reset-when-powered-externally
https://community.st.com/t5/stm32-mcus-boards-and-hardware/stm32f767zi-on-external-power-supply-is-stuck-until-reset-button/td-p/115194
And the user manual (UM1974) for nucleo boards where it states:

So it by default uses clock from the ST-LINK, X3 isn't assembled on the board and left empty.
It seems as it takes a while for the MCO to output the clock at power-on, with a reset the clock is powered on already and it therefore works.
This is also why it works if one connect the USB cable first and then power on E5V, then the clock pulse is already there and the board can boot up as normal.
If one doesn't want to be dependent on MCO one have to solder on the board to fit X3 and the capacitors and also set the correct solder bridges or use another external oscillator, or use the internal clock HSI.
EDIT:
If you don't care to much of startup time it is possible to increase the timeout for the HSE to wait for MCO.
In CubeMX this setting is found under RCC -> Parameter Settings -> HSE Startup Timout Value (ms).
I set it to 2500 ms and now my board boots at the first try with E5V and no USB connected.