Embodiments of a microelectronic package including at least one trench via are provided, as are embodiments of a method for fabricating such a microelectronic package. In one embodiment, the method includes the step of depositing a dielectric layer over a first microelectronic device having a plurality of contact pads, which are covered by the dielectric layer. A trench via is formed in the dielectric layer to expose the plurality of contact pads therethrough. The trench via is formed to include opposing crenulated sidewalls having a plurality of recesses therein. The plurality of contact pads exposed through the trench via are then sputter etched. A plurality of interconnect lines is formed over the dielectric layer, each of which is electrically coupled to a different one of the plurality of contact pads.