Postgresql streaming replication and wal archive?
Further testing revealed that the different WAL files were mostly those that had been rotated but not yet written to. The new slave would try to archive these (possibly fixed in 9.2) but they wouldn't be used for recovery. 

The other problem is the overwriting. We disabled the overwrite (instead storing with a new filename so we at least keep the WAL just in case) and everything works... both failover and later restore. 

NOTE: my earlier answer here that was completely wrong. See the edit log if you need to see how wrong.