A problem area in many cameras is not within the film gate/mask, but in the stretch between the film gate and the supply or takeup spool. I would start by checking the seals near the hinge side of your AE-1 for this one. The fact that the location seems near identical on every frame makes me think it isn't a lab problem. (I am assuming there is a dark spot on each negative; e.g., it's not a weird printing error.)

(This also reminds me, I need to replace the seals in the AE-1 I inherited from my dad.)