There is one strange and awful thing I don't understand about restore_command: it is always being called for every single WAL segment postgres wants to apply (even if such segment already exists in pg_xlog) until replica start streaming from the master.
If there is no restore_command in the recovery.conf - it perfectly works, i.e. postgres replays existing wal segments and at some point connects to the master and start streaming from it.
When recovery_conf is there, starting of a replica could become a real problem, especially if restore_command is slow.
Is it possible to change this behavior somehow? First look into pg_xlog and only if file is missing or "corrupted" call restore_command.