Also mit einem (einzigen) User hat es dann doch noch funktioniert.
Hab zum einen im WRKLNK über die Option 9 den Zugriff gewährt und für den User den bestehenden WRKDIRE Eintrag mit 2 geöffnet und gleich wieder mit Enter bestätigt.
Anschließend in Windows über NET USE * /DELETE alle Verknüpfungen gelöscht und nur diejenigen, die ich brauche mit NET USE X: \\server\verzeichnis /user:user-name und anschließender Angabe des Kennwortes wieder hinzugefügt.

Beim zweiten User hab ich die tolle Eigenheit, dass ich den Account an sich nicht über NET USE X: \\server\verzeichnis /user:user-name und Kennwort hinzufügen kann. Da kommt dann immer die Fehlermeldung Systemfehler 5 (Zugriff verweigert). Wenn ich den speziellen User über WRKUSRPRF mit Option 3 kopiere und aus (nur als Beispiel) TEST den User TEST2 mache, in WRKLNK den Berechtigungseintrag erfasse und in WRKDIRE für den User einen Eintrag anlege und sonst nichts ändere, dann kann ich ganz bequem ohne Fehlermeldung mit NET USE X: \\server\verzeichnis /user:TEST2 und Kennwort die Verknüfung hinzufügen.

Und das Verhalten hat sich nicht nur an meinem Rechner gezeigt, sondern auch am PC meines Kollegen. Es muss irgendetwas mit dem User an sich zu tun haben. Zum Testen davor hab ich einen Dummy Account angelegt und wie oben genannt die entsprechenden Einträge verfasst. Wollte wissen/ausschließen, ob der Access Denied Fehler an den Berechtigungen im *USRPRF liegt. Der hat am Anfang ganz normal funktioniert (also das Laufwerk hat sich mit Angabe der Credentials des Test-Users ganz einfach anlegen lassen). Nachdem ich für den Test User im WRKLNK den Eintrag gelöscht habe, ließ sich auch im Windows logischerweise für den User kein Laufwerk mehr anlegen. Nachdem ich den Eintrag wieder hinzugefügt habe, bekam ich für den Test User die selbe Fehlermeldung, wie ich sie weiter oben beschrieben habe. Darauf den User kopiert und wieder Einträge verfasst und schon funzte es mit NET USE und /user:TEST2

Aaarg... Gott sei Dank ist WE.
Hoff ich komm am Montag drauf.