TL;DR: Do not use secured view in the definition of a security profile
So Oracle deleted all records for such employee from the per_person_lists table, but the call to renew them did nothing.
The security profiles in question contain a subquery on per_assignments_f. That was a table, long time ago, in 11i, but is now a (secured) view in R12. So replacing the secured view by the base table resolved the issue.