>Is this on a local drive or a network drive?

Network. We created a separate network for testing, and in this new mini-network we've got the same results as in the live network, which is that the application running on Windows 8.1 will get one of those errors while the same app running on 8.0 will experience no issue, no matter what settings we change, what version of SMB we run etc.

[Update]

This Friday an ex-employee who retired came back as a contractor for some time, so the network guys set up a new computer and they used Windows 8.1 by mistake, and interestingly enough this particular user has no issues with 8.1 either, so we compared settings and the only difference was some policy that was not applied to this computer, but removing one of the 8.1 computers from said policy did not make any changes in the behaviour.