After a discussion on talk-is I contacted Íslandspóstur and requested permission to use their postal code records under an OSM-compatible license.

They said yes, which means we just have to write an importer for their data and survey the rest of the streets in their database before Iceland has complete postal code coverage.