Normally the area between the frames should be a lot darker, almost black in colour, and not the brown in your sample photo.
As you have mentioned about the lab in this post and in previous posts, they know what they are doing so I would assume it is not a processing problem. Just out of curiosity, the 110 film was processed in the same machine that 35mm films were processed?
When I look at the image in the negative photo, it appears underexposed. Of course, if it was underdeveloped then it would look similar but as you say the lady has a vast experience of C41 processing so I would go with what she says.
Sorry, I can't be of any better help.