Tesco et al will use automated machines and the only control they really have is the quality of the chemistry - If the QA checks are not being carried out correctly or on a regular basis, then results could vary. If you are not satisfied with the quality, try another lab. ag-photolab has a growing reputation, and Peak Imaging is well established (I've used them in the past to do 5x4 C41).

Scanning to CD is only as good as the operator & equipment - Might be worth selecting one frame and getting it printed by a Pro lab and then compare it to the scans you already have.