Poor regression results with LASSO which improves after variable selection - could someone shed some light on the observations?

Question

This is my first post here - I'm not a statistician by training though I have a machine learning background, so please correct any erroneous usage of statistical terminology if you see any.

Currently, I have a (linear) regression problem I'm trying to solve - ~5000 predictors and ~200 examples which is an extremely ill-posed problem. The predictors take on real values from 0-1, while the labels are integer-valued scores between 0 and 100 Ideally, the goal would be to get reliable estimates of the coefficients (betas), but out-of-sample mean-squared error is also a metric I'm interested in.

So far, I used the following procedure:

1. Split the data into 5 cross-validation folds.
   • For each training-test fold:
     1. Normalize the data using z-scoring on the training data, applying transformation to the test data
     2. Learn a ridge/LASSO model on the \training data with hyperparameter selection using cross-validation (i.e., a 2nd-level 5-fold cross validation and re-training with the best hyperparameter value)
     3. Evaluate model on the test data
2. Calculate mean model fit across all 5 folds

Unfortunately, this procedure is leading to very poor fit - the hyperparameter value that performs best in terms of MSE on the held-out data seems shrink all predictor coefficients to zero or nearly zero, both for the ridge and LASSO models, so I am essentially predicting the constant intercept term regardless of the input. My search space for the hyperparameters (regularizer coefficient $\lambda$ for LASSO and ridge, respectively) is quite large $(\{10^{-10}, 10^{-9}, \cdots, 10^9, 10^{10}\})$ so I don’t think that’s an issue. Rather, the models learnt for smaller values of the regularizer fundamentally don’t predict the out-of-sample data well.

After using a variable selection method of my own construction (which I will elaborate on in another question), I got much better test error rates - therefore there exists a subset of variables which allows much better fit than a constant mean predictor.

I'm wondering why the LASSO model was not able to select the right variables with good prediction error even with my hyperparameter selection procedure - could anyone provide any potential suggestions or insights as to whether it was some error on my part or an issue with the data perhaps that I have overlooked. Thanks!