(1) The year threshold for police certificates has nothing to do with the threshold for the residency requirement. It is regulated in a completely different part of the Citizenship Act. So let me say that again:
It is a complete coincidence, that until now the number of years for the PCC (4 years) was the same as the residency requirement (4 out of 6). To ask "if the residency requirement changed from 4 to 3, why didn't the requirement for the PCC change from 4 to 3" is as valid a question as "if the residency requirement changed from 4 to 3, why did the election cycle for the house of commons not change from 4 to 3"
Also: Beyond the fact that by law they aren't connected, why should they be? Canada cares that you didn't have any recent convictions in foreign countries. Why should that definition of recent be connected to the residency requirement.
(2) Police Certificate processing times depend highly on the country. For example, in Germany, you print a one-page form, go to any notary and sign in front of them. Then you send it off and you get the Police certificate within 10-14 days. If you are not as lucky to have lived in a country where PCCs are easy to get, then yes, it means a delay in your application. I totally get that it is annoying.
(3) There was no criminal background check for foreign countries (only for Canada) before 2015. The criminal background check was introduced around the same time as C-24.
But again: The PCC criteria have never been linked to the C-24 changes in the residency requirement.