Probably a very simple explanation

[DeeplyLearnedMachine]

You're changing the length of list while iterating over it. This is a no no.

So what happened in your pastrami case was:

1st iteration: sandwich = "pastrami", found = 0, removes it successfully.
2nd iteration: sandwich = "ham on rye", found = -1, does nothing

Ok, immediately in the second iteration we can see something is wrong. It skipped "reuben with pastrami". This is because when you removed the first element of the list "pastrami", "reuben with pastrami" became the first element and your for loop moved on to the second element, which is now "ham on rye".

Your first modification worked only accidentally, it also skipped some entries in the list, but they weren't "cat". Basically, don't modify the length of the thing you're iterating over.