Another update here to rule things out.

We tried digital and disk copies. No changes.
Other friends who also have day-one Xbox ones can connect to use without problem.

While it is 99.9% likely it is an Xbox to Xbox issue (as explained in my previous two posts), it is not tied to day-one xboxes, nor is it tied to the Operating Systems or media format.

This leaves only one possibility, something that is otherwise unheard of and exceptionally strange.
There is something, as to yet be identified, about certain Xbox systems not being able to connect to certain other Xbox systems with this title, and only this title.

There's a ghost in the machine, Will Smith style. We have no choice but to wait for the devs to find out what on bloody Earth it is, and patch their software to account for it.