Does the dark streak extend past the negative margins and into the perfery?
Does it happen on every roll of film?
Are the frames grouped together - say 4 frames at the beginning or the middle and the rest of the roll is OK? If they are grouped together does the streak happen every frame, every other frame or with some consistent gap between frames? You say the streak is always to the same side of the frame - but is it always in exactly the same place? If it varies, is the distance between the streaks constant?
Has the film been through any airport scanners?