Solved. (See my answer.)
I have a couple of startup apps using the desktop bridge. In the past they used to work fine. Now, probably after some Windows update, after a reboot they don't start when I first log on, and don't even appear in the startup tab in Task Manager. After I log off and on again, they immediately start, and also appear in the task manager.
More Info
They all use desktop:Extension Category="windows.startupTask".
And in sign-in options I have "use my sign-in info to automatically..." turned off.
EDIT
The issue resolved itself after the last Windows update July 2019.
EDIT 2
Spoke too soon. The problem is back. And it doesn't (always?) resolve itself after logging off and on. And it seems like after a couple of minutes (much more than the 10 seconds of startup delay) they do (sometimes?) appear in the startup list (but perhaps only after I start them manually?).
Isolating the cause was difficult because the problem seemed to manifest itself in a random manner. Sometimes solving itself, sometimes not...
The reason was that it was caused by a semi-external reason. I had an application that was registered as a startup app but wasn't "installed". It was still in development and was running from Visual Studio. And its drive was not available immediately when logging on. As soon as that drive would become available, that and the other startup apps would be added to the startup list.