Zoltan, You may very well be on the right track in suspecting hardware issues.
We recently experienced a problem with similar symptoms on a new TSM/3583 install. Although the messages were not identical to what you posted, a bad SCSI card manifested itself by library components disappearing mid-operation. We were getting messages referring to missing elements, no devices found to match what was defined for the PATH, and "medium not present" when a tape was mounted and already being used. You might want to run diagnostics on the card, and check that there are no issues with the cabling. Ted