The problem you're running in clearly indicates that either Network access restriction or Network access policies is configured for an user or group. Since you're positive that there is nothing configured on the NAR, lets narrow it down via logs.
Duplicate the issue again with both the devices (working and non-working)
With working devices, you would get the passed attempts >> copy and paste the log attempt as it is.
With Non-working device, you would see failed attempt >> copy and paste the log attempt as it is.
Regards,
Jatin
Do rate helpful posts-
~Jatin