Must the air gap in a transformer always be perpendicular to the magnetic field lines?
There already IS a gap between laminations &mdash; that's the whole point of using laminations in the first place, to break the circuit for eddy currents, reducing losses. The laminations are typically insulated by a coat of lacquer or paint.

And to answer your question, no, that gap has nothing to do with the gap required to prevent magnetic saturation, because the field lines do not cross that gap at all. The anti-saturation gap must intersect the magnetic fields lines in some fashion, but it doesn't have to be geometrically perpendicular.