Current word in the dev circles is that the device does in fact have 8GB of internal eMMC, but has been partitioned to use a faster/more reliable configuration, called SLC, which results in a practical capacity/density of 4GB of user space, with about 1.5 GB of bloatware installed.
More information on understanding eMMC accessible storage: See here -
http://tjworld.net/wiki/Android/HTC/EMMC/UnderstandingUserCapacity/
More information on previous uses of SLC in HTC devices:
http://forum.xda-developers.com/wiki/index.php?title=HTC_Vision#The_Missing_2GB
Is this confusing for an average consumer? Yes.
Is this worth complaining about? Sure, but everyone with this phone still has at least 1 week to decide they don't want it so I don't think anyone is 'owed' anything. At most you might be able to get out of the $35 activation fee, if you were charged one (and most of us with a business discount likely weren't).
Did HTC and/or Verizon lie about specs? Not if the above is true. (Think of a PC manufacturer selling a business class system with 2x640GB HDDs configured in RAID 1. Does it say 2x640GB, yes, is that accurate, yes, is there 1280GB of user accessible storage, no, since RAID 1 mirrors all data 2x for increased reliability.)