When forming sophisticated high-k metal gate electrode structures on the basis of a replacement gate approach, the fill conditions upon filling in the highly conductive electrode metal, such as aluminum, may be enhanced by removing an upper portion of the final work function metal, for instance a titanium nitride material in P-channel transistors. In some illustrative embodiments, the selective removal of the metal-containing electrode material in an upper portion of the gate opening may be accomplished without unduly increasing overall process complexity.