I had seen that with VM's, but never with bare metal.

This fixed some of our Macs and able to update afterward. Hope this helps.

launchctl kickstart -k system/com.apple.softwareupdated

To ask the stupid question. How often do your devices reboot? Its possible for the daemons to hang.

What does the install.log say? I have seen plenty of one off issues where a device or two wont update, but never a feet unless it was a bunch of VMs. Maybe network traffic is getting filtered, but the logs should give an idea.

I've had this issue with some of our mac's when the user that the update triggers on doesn't have Volume Ownership.
https://support.apple.com/en-am/guide/deployment/dep24dbdcf9e/web 

I have switched us to using S.U.P.E.R.M.A.N by Kevin M. White because of this and providing admin credentials via [--local-account=AccountName] [--local-password=Password] options that has volume ownership.
https://github.com/Macjutsu/super

This still requires the admin account to have a secure token/volume ownership.