How to un-install HTC's gingerbread ROM for Desire
The best known option for the HTC Desire is to use unrEVOked - http://unrevoked.com/recovery

unrEVOked has the added benefit of flashing in a version of Clockwork Recovery. That way you can just boot into recovery, do data wipes, and flash Cyanogenmod.

Note that there is a chance that Gingerbread could prevent unrEVOked from performing its usual processes. In addition, your previous rooting adventures could have placed an alternate recovery into the phone as well. I believe you can press Power+Vol-Up when starting the phone to invoke recovery mode. If Clockwork is present, you may proceed to flash away.