The legal limit on windscreen and front side windows is a lot lighter than rears - I'm pretty impressed that a tinting company would explain/suggest yours are close to the legal limit rather than just tint and take your money! Makes a change!!
Without a 'tintman' to measure the light transmitted through the glass on your particular car it's impossible to know for sure if you could get away with putting film on them. If the tints at the rear are fairly light, which it sounds like they are, then I'd leave as is and be smug in the knowledge you're fully legal
Not sure if the rules are more strictly enforced abroad than they are here, so may be worth leaving for your trip in any case?