Ok, this is to everyone still having trouble with the backupset
delete/expire problems.

This is information form Tivoli tech support, so don't shoot the messenger.

It is true that this was a bug in TSM 4.1.2, it seems that if you created a
backupset and it passed its expiration date, the volume that the set was on
could not or would not be able to be reclaimed as scratch. An addition of
the delete volhist type=backupset command was added but undocumented in
4.1.3, and the fix was implemented in 4.2 to remedy the problem.

The problem I was having was the undocumented feature of delete volhist was
returning an unknown volume error when I tried to run it.

The solution was as follow from Tivoli tech support:

delete volhist type=backupset todate=(the day after the backupset was
created) totime=(the same time) volume=(volumename in all CAPS) force=yes

The key was the all caps in volume=, (the volume parameter is case
sensitive)  I omitted the totime and was still successful.

Hope this helps.