Barcodes on your tapes are a good thing, generally speaking. But a barcode is not required to clean a tape drive.
Please be aware that each slot can individually be marked as a cleaning slot. It is a property of the slot, so you can have multiple slots marked as cleaning slots (although that is not advised). The purpose of marking a slot as a cleaning slot is basically to prevent it from being accidently inventoried and "wasting" a cleaning cycle.
Marking a slot as a cleaning slot is totally different than BE detecting a cartridge itself as a cleaning cartridge. BE detects a media as a cleaning cartridge either by bar code (which you don't have) or when it mounts it in a tape drive.
The "Physical Volume Library Media not found" error probably indicates confusion in the BE database about what is really in your library and not any sort of a tape drive or hardware error or issue. A full inventory of your library may clear that up.
I suggest forcing the drive to clean itself by changing slot XX (whatever currently holds the cleaning tape) back to a regular slot (not a cleaning slot) and then running an inventory job on jsut slot XX. A cleaning job from BE is nothing magical, it doesn't send any special commands to the tape drive, it simply puts that tape in the drive and lets the tape drive decide what to do with it.