When the NMOS is connected to VDD and turned off, why does it not block the current completely?
You have connected the NMOS transistor upside down. You have the source connected to the higher voltage, which causes the parasitic diode structure to be forward biased. Flip the transistor vertically.
In your second schematic, left side, you are using NMOS transistors to pull the output high. Since the gate voltage can't get any higher than the drain voltage, the source voltage can only rise until \$V_{GS} \approx V_{TH}\$. As many students have learned, you really can't make a non-inverting gate by using NMOS to pull high and PMOS to pull low.