Yes well sometimes we do have to tweak the image a bit to get the best results, thats one of the main reasons that doing hard proofs is also useful. Depending on the paper/process involved it could even be that they had gone a bit long on the developing chemistry. Exhausted chemicals can cause all sorts of problems, from under development right through to colour casts. Finding a lab with good QC can sometimes be just as important as price. Many labs will have multiple machines with different paper types in them, so while one machine is turning out good prints, other paper types may have issues. Get the prints run through when the machine has just had the chemistry refreshed and they will likely turn out OK. Thats why caring about things like QC are important, as there are many variables that the lab needs to keep on top of to consistently turn out good images. It was the same when I used to do my own printing at home in the darkroom, lots of things to pay attention to to get consistently good results. Although I am quite lucky in that I seem to have found a lab here in the UK that has very good QC and is also really cheap too.
What I would do is if some of the prints are OK and others are not, I would complain to the lab about it. From what you are saying in your second post I would try that first. If the good prints you got back matched the soft proof, then I would expect all of the prints to match the soft proofs. If it's dark but otherwise OK maybe its down to you, but if it's as you say meh, and muddy looking I going to suspect the lab.
Alan