Peter- Does your library have more than one tape drive?
Does this behavior (media set hopping) happen with every single backup job? Or do the first jobs work correctly and the jobs that run later at night exhibit this behavior?
My thought (and I may be way off) is that your settings are OK for what you want to do, but the behavior of backups spanning more than one tape may be throwing your media set scheme off a bit. If a job is appending to an existing tape and then needs to continue to another, the 2nd tape must be overwritten from the very beginning. So, in your case, you created 2 media set#1 tapes and through the night some media set#1 data has been written to both of them. Then one of the jobs needs another tape- there's no overwritable media set #1 tapes; so it will use a yet to be used media set#2 tape (even though there's room left on a media set #1 tape).
Just a thought I had.
Partitioning as a concept is making smaller libraries out of a big one. You partition the slots, which effectivly limits the avaialble pool of tapes a backup job can even consider to use for the job. If you review this forum you'll see various schemes used like parttions to control which tape gets used each day of the week, or seperating daily backups from full, or tapes that stay in the library vs. tapes that get rotated. Some people want to be able to pick up a tape and know exactly what server backup it contains. Others want their tapes divided by dates. What do you want to do?