Oracle OS Authentication only works on certain databases/clients
Fixed the problem:

The source of the problem was that the broken clients and server were referencing a central TNSNames.ora file on a different file server. This was intended; however, I did not know that this also makes those machines search the sqlnet.ora there.
Someone - or some installer or something - placed an empty sqlnet.ora file in that central location. I haven't tried if the clients only ignore their local files if there is a central one, but in this case any changes to the local sqlnet.ora files had no effect.

Adding the line

SQLNET.AUTHENTICATION_SERVICES = (NTS)


to that central sqlnet.ora file obviously fixed it.