This means that if you do some cleanup or something when deleting pages, your code won't run when someone mass deletes the contents of the Recycle Bin.
Is this a bug, or am I doing something wrong?
You can change this behavior by setting the operationCompability to "PageStoreDelete" in EpiServer.config
I confirmed that this works. Can you give some more background on this -- why does this setting exist? Are their are side effects? (I mean, it has to be this way for a reason, right?)
I got this explanation back from support.
They included that flag for compability and performance reasons. Apparently they didn't list every child (when deleting) because of performance, but in the later releases (later than R2) they had to revert back to the old behavior of listing every child because of a bug with cache invalidation. So if you have CMS 6, there shouldn't be any performance issues enabling the old behavior at all.