The law in Iceland dates from the 1940s, and is modelled on Danish laws of the period.
Pre-1940, an adult convicted of a serious crime (one which is "outrageous to public opinion" and leads to a prison sentence of 4 months or more) would lose their "honour". This had various consequences, including losing the right to vote in Althing elections. The 1940 law allowed for convicted felons to regain their "honour" and register to vote. The process of restoring one's reputation required three letters of recommendation.
Restoring one's honour does not clear a person's criminal record but it can restore certain civil rights. Iceland now does not withdraw the right to vote from felons, but an untarnished reputation is required to hold certain public offices, or a law licence. Directors of public companies must also have a clear reputation.
The restoration of honour is not the same as a pardon, the crime remains on record. The letters of recommendation need not come from a high-ranking member of the government, but from one with good standing in the community. The applications are considered on a case-by-case basis by the Ministry of Justice.
This is discussed in an article http://icelandmonitor.mbl.is/news/politics_and_society/2017/09/15/laws_for_restored_honour_are_77_years_old/
If your Icelandic is up to scratch, look at the full text of the law: https://www.stjornarradid.is/verkefni/log-og-rettur/fullnusta-refsinga/uppreist-aeru/