Is it possible that this effect is too strong to be compensated?
You might have the right idea, but from the opposite direction. Because what soft-proofing does is preview the limitations of the medium represented by the profile. In other words, if you adjust colors and tones on the screen but the soft proof doesn’t visibly change, that means you’re adjusting beyond the range of what the printing process can reproduce, and the soft proof is simply telling you the truth about that.
If you could view a graph of your RGB profile vs the printer profile, you might see that the range of colors possible in RGB is different and generally larger than what can be reproduced in a print. If you are on a Mac, you can visually compare the two profiles yourself using ColorSync Utility.
What kind of printing process does the lab use? Are they using inkjet, digital press, chemical color print…? You might mention your situation to the lab, and ask, “What photo printing service do you provide that offers the widest tonal range and color gamut?” Just be aware that no printing process can exactly match a computer display, and vice versa.
Even when printing at home, the intensity of color and contrast depends on which paper and ink combination I use. Usually, the more I pay, the closer it can match the display. Less capable papers and inks have a narrower color and tonal range, so soft proof shows me that in advance. At that point, the game is not to try and match what I see in RGB, but to make the image look its best within the limits of the medium I’m soft-proofing for.