We report mid-infrared LiNbO3 depressed-index microstructured cladding waveguides fabricated by three-dimensional laser writing showing low propagation losses (~1.5 dB/cm) at 3.68 µm wavelength for both the transverse electric and magnetic polarized modes, a feature previously unachieved due to the strong anisotropic properties of this type of laser microstructured waveguides and which is of fundamental importance for many photonic applications. Using a heuristic modeling-testing iteration design approach which takes into account cladding induced stress-optic index changes, the fabricated cladding microstructure provides low-loss single mode operation for the mid-IR for both orthogonal polarizations. The dependence of the localized refractive index changes within the cladding microstructure with post-fabrication thermal annealing processes was also investigated, revealing its complex dependence of the laser induced refractive index changes on laser fabrication conditions and thermal post-processing steps. The waveguide modes properties and their dependence on thermal post-processing were numerically modeled and fitted to the experimental values by systematically varying three fundamental parameters of this type of waveguides: depressed refractive index values at sub-micron laser-written tracks, track size changes, and piezo-optic induced refractive index changes.