PostgreSQL WAL file database system identifier wrong
Can it be what archive already filled with WAL from another installation? Postgres documentation specifies that archive_command should not overwrite WAL files in archive (https://www.postgresql.org/docs/9.6/static/continuous-archiving.html):


  The archive command should generally be designed to refuse to overwrite any pre-existing archive file. This is an important safety feature to preserve the integrity of your archive in case of administrator error (such as sending the output of two different servers to the same archive directory).


So if archive is set up correctly it will refuse to override WAL and restore will fail.