That patch worked. I've successfully setup things.
@d19dotca So far things seem to be fine, didn't get the issue yesterday at all, and so far nothing today neither.
The order in that specific case was apparently a bit random based on the result of the network queries we performed in parallel before. I've put a fix to now always sort by fqdn to fix this.
Thank you @girish, this worked for me too