If the problem is getting "lucky" on a test set, then it seems like you could do several rounds of splitting test/training set, retraining from scratch each tim

If the problem is getting "lucky" on a test set, then it seems like you could do several rounds of splitting test/training set, retraining from scratch each time, and then take the median performance. Not great if training takes a long time, but it would at least conclusively answer the question.