You say exactly what I want to say. I'm living in South Korea now, I tried many ways on December 2019 to get it but it didn't work, even I asked my Korean friends to help anyway (go to police station of cities directly, call 182, call many police stations to ask) but they refused to issue Criminal (Investigation) Records Check Reply (범죄· 수사경력 회보서) because of recent changes to the Personal Information Protection Act. They just accepted to issue Background Check (Criminal Records) Certificate (신원조사(범죄경력)증명서). And they explain that police officers can search records for Korean citizen, but they cannot search records for foreigners.
My husband also called Canada Embassy for helping, they know the issue because many people contact them for this but they don't have any solutions.