where are you getting the film processed? Some commercial processors, especially cheap ones, are not all that good at keeping their equipment clean. Just before the local costco quit doing film i noticed my film from them coming back pretty scratched up.
Try some black and white and soup it yourself, or just run a roll through the camera, rewind it, take it out, open the can and inspect the film. This way you eliminate the camera, or confirm it.