Ok, lets give this a try.
The android screen you went to by holding the volume down and the power button, that is called the hboot, or bootloader screen. Has a picture of Andy riding a skateboard at the bottom.
OK, now while on this screen use the volume buttons to highlight RECOVERY , press power to select.
Wait a hot second until a red triangle with an exclamation mark appears, this is normal. This is the stock recovery.
Now press and hold both volume up and volume down and press and hold the power button all at the same time. You should be taken to another menu, this menu should have a few options. I don't have the HD, so your options may differ slightly.
In here there should be an option to Wipe or CLEAR CACHE, press power to select.
There should also be an option to CLEAR STORAGE, press power to select this as well.
Then select REBOOT, or just pull the battery and re-insert, then reboot.
See if that works, if not we may need to find a copy of the official RUU and get it on your SD card. From there we can flash it from the stock recovery, if it's indeed the official RUU with HTC's keys.
In the mean time, I'll PM our resident HTC guru...Scotty
"Not everything that counts can be counted, and not everything that can be counted counts." Albert Einstein