Fair point. I had tested that delete/restore had worked, it's just the "what are you deleting" criteria that I'd missed. Our test environment didn't match production that closely so the difference in data is what bit me.
That's the big, and more subtle lesson: it is really important that your test environment be very similar to production.