Just to confirm, I've made the scans myself and it's not an electronic issue. Scanning the same frames produces the same results and frames developed elsewhere scan fine.
I tend to agree that it's the lab and not the camera. But, like the first reply from markbarendt, I wondered about the straight lines. I thought that it might be something to do with the film rubbing against something.