In heterogeneous lipid membranes, the lateral organization is coupled to local curvature as the membrane bending energies depend on composition. We investigate phase-separated vesicles of ternary lipid composition in contact with structured surfaces, where the distinct elastic properties of the Lo and Ld phases come into play. We show that fused silica substrates with microstructured grooves induce sorting, alignment and deformation of Lo domains in adhering vesicles. The same phenomenon is observed on flat, chemically modified substrates with alternating stripes of rough and smooth regions. In both cases it is the Lo phase which accumulates over the smooth substrate and membrane-spanned groove regions respectively. Deformation of Lo domains occurs when domain diameters grow beyond the width of the microstructured stripes. Domain alignment was also observed in binary membranes featuring gel and fluid phase coexistence showing the generic character of domain sorting on microstructured surfaces.