Hi George,
after a few trial and errors, I can say that it's possible to unassign users from programs and delete their completion record altogether. However, not in every case, which requires some additional work to be done in preparation.
We use dynamic audiences to enrol users to programs and what I "discovered" is that once a user is no longer part of that audience (for example, they change the value of a profile field which is a condition for being included in the audience), their record ceases to exist in the program completion report (and this program disappears from user's Record of Learning). So in the end, it is as if they were never enrolled in that program.
If the user is deleted (leaves the company), although that user is then no longer included in the audience, this record is not lost, exactly as you advised, but remains in program completion report. And yes, that is very convenient for keeping records used to prove compliance.
What I found not so convenient is that a user has to have a due date far enough in the future for me to unenroll them this way. Once they are overdue, or even 7 days before the due date, excluding them from a relevant audience will not be sufficient to unenroll them from the program. I'm not sure if this is how it's meant to work, but it creates additional workload for me as an administrator because I have to enrol them via a different audience with a longer due date because only after that is done, I am able to unenroll them. Silly, but works.
When the decision who needs to be enrolled to which training is changing in an organisation and accurate reporting is required as well, this may prove a very admin heavy type of work.
I don't know if anybody else faced similar issues but just wanted to share what proved to be an only solution in my case, although labour intensive one... If anyone found any easier solution, it would be nice if they shared :)
Best,
Vlad