Looks like a local user is required in the system called sshd, but fails to be created (which is expected to fail)

"OpenSSH for Windows" version
8.6.0.0

Server OperatingSystem
Windows Server 2016 Standard

Client OperatingSystem
N/A

It looks like the server requires a local user be setup called sshd. This is not documented well.
The install may attempt to create the user locally, but the password complexity in my domain is so high that any basic creation script MUST fail.
There is no report of any failure during install or run. What happens is, when you run the sshd.exe as a service with Local system account, it just hangs for roughly 5 minutes. After 5 minutes it finally starts up and works fine. My speculation is, the process attempts to find the local username sshd and attempts to convert the name into SID. As the user does not exist, it just hangs.
If turn on debug, it looks like this:
debug1: get_passwd: lookup_sid() failed: 1788.
or with older versions
debug1: get_passwd: LookupAccountName() failed: 1788.

This error message will point you completely wrong direction as it will guide you to search some problem in the domain trusts.
The issue has nothing to do with the domain trusts.

I've simply created a local machine user called sshd and put a very long password there as required by my domain.
Once done, all works fine immediately.

As an indication, you may compare the time between service start and the time when you find in the log file the message
Server listening on 0.0.0.0 port 22.
In my case it was something around 5 minutes. It wouldn't be so bad if this was a one-time issue after startup, but it looks like the problem is there whenever the process needs to fork. It will trigger another 5 minute interval. That makes the overall solution very problematic.

Start by reproducing the Windows service startup and fork delay, then compare the timing with the log entry for “Server listening on 0.0.0.0 port 22.” Trace the get_passwd and lookup_sid/LookupAccountName messages to determine how a missing local sshd user is handled; done means the cause is accurately reported or documented and the repeated delay is addressed.