See Re (tilly) 2: An odd flat file database question for an explanation of the bug in your code. In any case the problem is a data structure issue. Keeping a sorted list may be convenient for spitting data out, but is inconvenient when it comes to inserts and deletes. The simplest answer in this case is to use a BTree with DB_File setting the R_DUP flag on. You cannot get the features you need through the tied interface, but the OO interface gives you the ability to quickly access by catalog ID, insert and delete, and have duplicate entries.

Of course if the complexity of the problem grows a more sophisticated database would be a better fit...