안녕하세요,
테스트시에는 이미 진행해보신 아래 레지스트리 값을 제거하면, 실행창 기록이 삭제 되는 것이 확인 됩니다. (재부팅 필요없음)
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\RunMRU
다만 작동이 안되신다면, 다른 정책이나 보안 프로그램에 의해 발생할 수 있어 보입니다.
아래 링크는 말씀하신 정책에 대한 내용입니다. 임시로 설정을 변경하여 확인해 보시기 바랍니다.
감사합니다.