One illustrative method disclosed herein includes, among other things, forming a plurality of trenches in a layer of insulating material, performing at least one damage-causing process operation to selectively damage portions of the insulating material adjacent the trenches, forming a conductive line in each of the trenches, after forming the conductive lines, performing a selective etching process to selectively remove at least portions of the damaged portions of the insulating material and thereby define an air gap positioned laterally adjacent each of the conductive lines, and forming a capping layer of material above the conductive lines, the air gap and the undamaged portion of the layer of insulating material.