@Tadej Šivic, Thanks for posting in Q&A.
From your description, I know you have trouble in zero touch enrollment.
To clarify this issue, please check the following.
1.How many devices were affected?
2.Check whether the devices meet Perquisites and make sure that Managed Google Play's status is normal.
https://support.google.com/work/android/answer/7514005#zippy=
Non-official, just for reference.
3.Try to factory-set the device and to see if the issue can be fixed.
4.Utilized mobile data from various carriers as well as Wi-Fi connections.
5.Completely removed the devices from the Zero-Touch portal (https://partner.android.com/zerotouch#) and subsequently re-added them.
Also, here is a link about zero touch enrollment guidance you can refer.
https://smbtothecloud.com/get-started-with-android-zero-touch-and-intune/
Non-official, just for reference.
Please try above information, if there is any update, feel free to let me know.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.