I think that it's OK to use the past simple in the second clause. Saying "they all failed" means that you are focusing on the separate attempts of each of these people. These various failed expeditions all took place in the past - in finished time periods - so it is appropriate to use a past simple to refer to these individual attempts. Saying "they have all failed" would imply that you are grouping the failures together to make the point that there has not yet been a successful attempt.

Something important that you need to take into account is that when using a tense in a sentence, you should sitck to it. The example that you're providing is good since the tense of the sentence is present and its aspect it is PERFECT. Even though, a person could say the second sentence and will be understandable.

Generally, the difference between the two tenses is the present perfect has some sort of effect on the present, sometimes implied , sometimes explicit. That is the case here. The version with the past simple is more factual while the version with the present perfect has some sort of additional effect on the present which would be understood from context. Could be an element of fear or danger based on the sentence, but I'm just guessing.