To perform the base backup, I am using the pg_basebackup tool:
pg_basebackup --format tar --xlog -D - | gzip > ${BASE_BACKUP_FOLDER}/base_backup.tar.gz
After making a base backup, I made some changes on the database, including creating new tables and adding data to them. Then I moved the data folder to a safe place, restored the base backup, created the recovery.conf file, copied the WAL files that were unarchived back to the restored data folder, and restarted postgresql.
The idea was to remove WAL files that are no longer needed, WAL files that are someway included in the base-backup. Any way, that was not the problem, as I tested the same procedure without the archive_cleanup_command.
Pedro
The restore procedure worked like a charm, and all data was recovered.
Then I created some more tables and added more data. Then made the same restore procedure as before, using the same base backup. Apparently the restore was successful and without errors, but the newly created data was not restored, only the one which was created before the first restore.
If your previous use of archive_cleanup_command deleted files that the new recover would have have needed, then the recovery would have to end at the first missing file.