“‘Network Drive’ refers to a location that is unavailable” while UNC works

Situation:

• Environment is a Windows Domain with 160+ Clients, several DCs. No WINS. DNS working.
• Fileserver is a Windows Server 2012 R2, patched regularly, SMB shares, proper NTFS and share permissions.
• Clients are Windows 7 x64 machines. Clients get drive mappings via Group Policies.

Problem:

Random users receive the error message "Z:\ refers to a location that is unavailable. …" when they want to create a new folder. Accessing the folder over Windows explorer works. Also renaming of files and folders works. Creating new folders and files works also in Windows Explorer, when the location in question is accessed over UNC paths. Creating new files and folders also works when accessing the drive mapping via a program such as DoubleCommander. Also saving files from Office applications to the network drive works.

Our measurements included:

• deleting the drive mapping and creating it again
• verifying the correct order in HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\NetworkProvider\Order
• rebooting server and client
• uninstalling antivirus software from client (none on server)
• accessing the drive from other profiles from the same PC (same error on some, works for others)
• creating folder from cmd (works)
• accessing the drive from the same user on another PC (works)

I appreciate any advice on how to track this down further.