If you were to buy an Evo 4G today, it would come with a locked bootloader (NAND protection on). Furthermore, because they are shipping with 2.3.3 now, there is NO root exploit. So it's incorrect atm to assume an Evo 4G is unlockable the instant you buy it.
As far as HTC's recent (May 26) promise to unlock bootloaders, they announced yesterday to Sensation owners that they are finalizing an OTA that will unlock the bootloader.
What that actually means is unclear, since the term "locked bootloader" is ambiguous to begin with. It could refer to a bootloader with NAND protection, or it could refer to the worst case scenario: a bootloader signed with an encrypted signature.
My gut feeling is that they will be removing the encrypted signature. Whether or not the E3D ships with the "unlock" is irrelevant. It can be retroactively be "unlocked" with an OTA, and HTC's pledge applies to all phones, even the ones already released. I believe that would satisfy the OP's requirement.
Removing NAND protection will come when the phone is rooted, which is trivial compared to the old prospect of having an unlockable bootloader like that of the Droid X.