Does stronger regularization always improve performance on testing set?
Title question
The answer to the title question is a pretty clear-cut &quot;no.&quot; For any fixed dataset, taking sufficiently strong regularization will make the linear model essentially constant, presumably not the best model.  Like most other things, there's a bias-variance tradeoff: increasing regularization weakens the model's ability to learn the training data, which to a point will tend to prevent overfitting and improve test performance.
Your more specific context
Word embeddings are substantially different from the other two, so the optimal regularization strength is probably mostly unrelated.
Between bow and tfidf, if nothing else the scale of the features will be larger in bow, so if you're not scaling, the penalties will be larger and the optimal regularization strength is likely to be smaller.