It is because, in version 9, the implementation of Plot is loaded from a dump file on its first usage, rather than loading when the kernel starts. One can see this by clearing the ReadProtected attribute:
ClearAttributes[Plot, ReadProtected]
Information[Plot]
(* -> Plot := System`Dump`AutoLoad[
Hold[Plot], Hold[syms], Visualization`Proto`
] /; System`Dump`TestLoad *)
where syms is a large sequence of symbols (including Plot itself) whose usage will cause the dump file containing the Plot implementation to be loaded, if it has not been already. The file in question is (as Visualization`Proto` suggests):
FileNameJoin[{
$InstallationDirectory, "SystemFiles", "Kernel", "SystemResources", $SystemID,
"Visualization", "Proto.mx"
}]
Since the definition of Plot needed for the autoloading functionality constitutes a single ownvalue, it does not matter whether Attributes[Plot] contains HoldAll or not, because there are no downvalues defined at this stage. After the full implementation is loaded, the attribute becomes necessary and therefore is set, but because heads are always evaluated before bodies, HoldAll is effectively present from the start. We can observe the same behavior in this example:
f := Function[Null, Null, HoldAll];
f@Print["evaluation leak!"] (* does not print anything *)