I have Backup 11d running on Windows 2003 Server. I have 8- or 16-magazine Quantum Superloader 3 autoloaders, and their cleaning jobs run 5-6 minutes at most. If it’s going beyond 10 minutes, I think you might have other issues there.
I had a problem like you described in the past, twice in fact, but the resolutions both times were different.
First time, I ran firmware updates on both the autoloader and the drive itself within, and that cleared up the problem.
Second time, I was getting repeated error messages pertaining to being unable to load and thread the cartridge. This happened with any tape, not just cleaning jobs. Quantum ended up classifying it as a chassis/drive failure and sent me a replacement.
I’d check out the possibility of firmware upgrades, based on the fact that your backup jobs are running, and also check the cleaning tapes themselves (ie, are they old, how many times out of their maximum # of uses have you used them.)
(Additional note by BW) When I had the first listed problem, the one solved by firmware updates, it was precisely as you described. It would go to about 10-12% and then hover at that point. There were never any error messages. The second problem, that was a replacement, the job would get to 100% and only then were errors displayed. This even more leads me to think you might be able to resolve it with firmware updates.