Your lab is ignorant of the truth of this matter, or just lying. You should ask your lab's manager to take a look at Kodak data sheet CIS-184:
http://www.kodak.com/global/en/professional/support/techPubs/cis184/cis184.pdf. It talks about doing C-41 film in E-6 chemicals, but it may soften them up. E-6 film in a C-41 process is even "safer", based on my own developing results, though I can't seem to find any online Kodak documentation to prove it. I don't replenish when I do C-41, so I have a 60 roll capacity. I have done two dozen rolls in a gallon of chemistry cross processed, and the rest normal. There weren't any problems at all with the normal C-41. I have processed C-41 and E-6 films in the same tank and nothing bad happened.
If it is that much of a problem, you can consider getting your stuff via mail from Freestyle, or whatever the European version of Freestyle is. (Fotoimpex???)
Good luck!