You would seem to be up the creek without a paddle.
Usually, when a large unix shop has a dedicated backup server, it will acquire some software to handle things. We use Veritas Netbackup and I have to say it is a dream. But it should be, we spent several hundred thousand dollars on our backup system. (You did ask how everyone else does it.)
I'm not a linux expert, but in mainstream unix, cpio was the first program to be able to handle multiple volumes. At some point, tar picked this up also (I think it was a Posix mandate.) And the BSD backup/restore programs can handle multiple volumes. And OSF introduced pax which can handle multiple volumes. Since you're running linux, you may have some other options, I'm not sure. But if you want to handle multiple tape volumes, the tape drive must be opened by a program that can handle multiple volumes. dd cannot.
One option is to give up on multiple volumes. Figure out how much will fit on a tape and then run several jobs. Each job will write to a single volume. You will need to monitor this solution closely to make sure that each job always fits on its tape.
The other option that I see for you is to remote mount the fileserver's files onto the backupserver. I gather that you tried this and ran into permission problems. Although I have never used linux, I believe that the permission problem can be solved. Typically very special steps are needed on the fileserver to enable remote root access to remotely mounted files. If you detail the steps that you used to accomplish the remote mount, I'll bet that one of our linux experts can help you out with this.