To me, I always thought it meant wipe everything except the sd card--"data, system, boot, both caches, sd-ext, .android_secure, factory reset. Just wipe it all except the sd card.
Now since moving to the S3, I just factory reset, wipe cache, dalvik cache, then flash the rom. But the S3 recovery is TWRP or CWM, which works fine on the S3.
On the Evo, the best recovery is the AmonRa or even Smelkus recovery.