The Control Panel Log doesn't seem to record this type of activity. Am I missing something?
Not natively, no. But there are various extension hooks that you can tie into with a custom module to easily log to a file or database table.
If this issue is occurring on a frequent/regular basis, you could remove delete privileges from that member group to see if the issue goes away.
If you remove delete privileges, you can still accomplish taking content offline using Status.
status==closed should disable content from appearing. Typically your editors should not be able to delete anything from the site, for reasons like this. They should have the power to take content off the site, but that's a much different action than a delete.
You could also see if Better Workflow supports more fine-grained options or the feature you're looking for.
You can use OmniLog together with custom extension as suggested by Michael.
The Control Panel logging solution is really missing for EE. I have a customer with problems similar to yours and also having hard time figuring out who's causing the problems. I think I will develop something eventually, but that's not my top priority for now.
I just posted Audit on Devot:ee. An add-on that tracks additional activity in the Control Panel, including entry deletes.