The question says:
To naturalize and become a citizen of your new country, I believe you need to get a police report or something of that sort from your old country during the naturalization process, even though you've been living in your new country for many years.
That does not seem to be generally correct. At least I can find no l;aw or regulation to this effect.
For the specific case of Spain, the relevant Wikipedia article states:
Spanish nationality can be acquired by naturalization, which is only granted at the discretion of the government through a Royal Decree, and under exceptional circumstances, for example to notable individuals.
Also, any individual can request Spanish nationality after a period of continuous legal residence in Spain, as long as he or she is 18 years or older, or through a legal representative if he or she is younger. Under Article 22, to apply for nationality through residence it is necessary for the individual to have legally resided in Spain for [various periods from one to ten years depending on prvious citizenship and other factors] ...
In addition to meeting the residence requirement, applicants must pass the DELE [a test of Spanish language skills] and a cultural and historical knowledge exam called the CCSE (Conocimientos Constitucionales y Socioculturales de España).
Article 22 of the Spanish Civil Code gives the requirements for naturalization. Neither the Wikipedia article nor the Code section mention any requirement for a police report or anything similar from the source country.
Natural;ization procedures and requirements are very much matters of specific national law, and there is no general rule for what is or is not required. Without a specific country to check the laws of, there can be no useful answer to this question, but many countries are aware of the kind of situation described in the question, and no doubt have procedures for dealing with such cases.