Methods of forming trench isolation regions include the steps of forming a semiconductor substrate having a trench therein and a masking layer thereon extending adjacent the trench. The masking layer may comprise silicon nitride. A recess-inhibiting layer is then formed on a sidewall of the trench and on a sidewall of the masking layer. Next, a stress-relief layer is formed on the recess-inhibiting layer. This stress-relief layer extends opposite the sidewall of the trench and opposite the sidewall of the masking layer and may comprise silicon nitride. The trench is then filled with a trench isolation layer. A sequence of planarization or etch-back steps are then performed to remove the masking layer and also align an upper surface of the trench isolation layer with a surface of the substrate. At least a portion of the masking layer is removed using a first etchant (e.g., phosphoric acid) that selectively etches the masking layer and the stress-relief layer at faster rates than the first recess-inhibiting layer. The recess-inhibiting layer is formed directly on a sidewall of the masking layer in order to limit the extent to which the outer surfaces of the stress-relief layer are exposed to the first etchant. In this manner, recession of the stress-relief layer and the voids that may subsequently develop as a result of the recession can be reduced. Multiple thin stress-relief layers may also be provided and these multiple layers provide a degree of stress-relief that is comparable with a single much thicker stress-relief layer.