I would do the quick format and then let backupexec assign the media sets when the job starts.
If the tapes have exceeded the overwrite protection period by the time they are rotated back into the library- you shouldn't have to quick format them (would still need to do Inventory or Scan)
It may be that I don't understand what you are trying to solve: Is it A.) that the backups don't work because they can't find tapes to use. Or is it B.) That the backups are not using the tapes that you want them to use for the job?
Problem A.) is a media set / job definition problem.
Problem B.) is a partitioning / job defintion problem.