An update :
Bug 3844804 has been filed. It is supposedly fixed in 10.2.


Per Oracle development :
"Thanks for providing a good debugging traces. We have found the problem.

We found that this problem can happen with DELETE command using option BACKED UP .. TIMES.

For eg. DELETE ARCHIVELOG ALL BACKED UP 1 TIMES TO DISK

can delete archivelog that aren't backed up when an archivelog is created during this command.

Workaround
==========
Use COMPLETED BEFORE option with BACKED UP option. For eg.

DELETE ARCHIVELOG ALL BACKED UP 1 TIMES TO DISK COMPLETED BEFORE 'SYSDATE-1';

This will make sure that RMAN doesn't delete the archivelog that was created during past one day.

Bug is fixed in Oracle 10g (10.2)"

================================================

ME :
As for the workaround - has the proposed solution actually been "tested"? I know what the new command/syntax means. But has it been tested? Did development prepare a test case that caused the original command to fail and the new command to work as expected? Or did they figure it out intuitively from the debug files? If so, I'd like to see the piece of code that helped them nail the issue. I just want to make sure that the proposed solution actually works. I
don't want to be in a situation where after a couple of months, I run into the same thing again (despite the new rman command)."

ORACLE SUPPORT :
Neither Development nor I were able to create a reproducible test case. The problem was found from the debug information you provided.

As for the 'piece of code' they found to be the issue, this is Oracle proprietary information and can not be shared.