So, I didn't have time much to investigate in too much detail, yet. A quick "dmesg | grep brcm" didn't show any differences between working and non-working boot.
I thought to try and see if the problem disappears when switching from 5 GHz WiFi to 2.4 GHz WiFi, but no difference.
However, now having both 2.4 and 5 GHz WiFi SSIDs set for auto-connect, I have a working workaround: after a "faulty" boot connecting to the previous WiFi will fail. However, now due to the second available WiFi, LE will connect to the other one and vice versa. So at least I'm left with working WiFi after each boot, no matter if faulty or not.
But WHY the connection to the previous WiFi fails, is still up for investigation when I have more time again.