Splitting hold-out sample and training sample only once?
In general, it's a good idea to split up your data into three sets:


Training Set (60-80% of your data)
Cross-Validation Set (10-20% of your data)
Test Set (10-20% of your data)


When you select a model using only a train and test set, you are selecting the model which performs the best on the test set after. This seems reasonable at first, but this is usually an overly optimistic estimate of your model's generalization error. This is because you are essentially fitting your model to another parameter $d$, where $d$ is your test set.

In order to address this problem, you can train a model on your training set and then choose the model that performs best on your cross-validation set. Now, this model is no longer fit to the test set and you can safely estimate the generalization error on the test set.

It sounds like you are already following this approach in selecting the model by choosing which one performs best on a 10-fold cross-validation on your training set. In this case, the error on your test set should be a good estimate of generalization error.

You also mentioned that randomness might affect your training due to outliers in your training data:


  ...as the 20-80 split of hold-out versus training sample is only done once, and thus might be too subject to randomness.


In machine learning, it is often assumed that our data is iid (independent and identically distributed) from some unknown distribution. On average, we should get data points that are representative of this distribution when we split up our data. A common practice to better ensure this is to randomly shuffle the entire dataset before splitting up your data.