Am I using GridSearch correctly or do I need to use all data for cross validation?
Your procedure is, from what I can tell, correct. You are correctly splitting your data into train/test, and then using your training data only to find optimal hyper-parameters. Using all of the training data and the hyper parameters found in cross validation, you are then evaluating your final model on the test set. 

Indeed, the outliers and the size of your dataset are the most probable causes for the large differences between validation and test. Basically, if the majority of these outlier observations fall in the test set after your initial splitting of your data it is highly likely that your test set scores will be larger than your validation scores. On the other hand, if these outliers are in your training set, you would expect the opposite to be true. This is because, regardless of what data your have in your training set for any random partitioning, these outlier observations are unlikely to be predicted well regardless of what you do, and because the size of your dataset is so small, these outliers will heavily impact your error estimate (especially with RMSE that is incredibly sensitive to outliers due to the squaring). 

Either way, report the test set scores only as your final estimates if you want to be honest.

In scenarios in which the variance is large in my test set scores (usually due to a small data set and a large number of outliers), I would highly recommend repeating your entire model building procedure as you described but with a different seed each time (i.e. split your entire dataset into train/test with a different seed each time). Do this until you run out of patience or the variance in your estimate of model performance is small enough. Maybe form bootstrapped confidence intervals from these repetitions to give you information on how much your model's performance varies.