When trying to map a network share from a server, I encountered some strange issues:

System error 64 has occurred. - The specified network name is no longer available.

System error 58 has occurred - The specified server cannot perform the requested operation.

After some heavy lifting and thorough detective work, I found what looks like the culprit. We are using several GPOs for the servers, and one of these were requiring the Microsoft Network Client to sign all communication (Always). I therefore had to override this setting, in a winning GPO (with higher precedence).

After this change, a “gpupdate /force”, and a restart, the net use command worked like expected again.