aeallison, here's my take:

Should we ban these folks again as we learn of their return?
Not always.. take d0pp for example. He wasn't a bad member really, he asked to be banned.

Would it do any good?
Nope. My proof? One word.. MemorY. (sorry man, but your the poster boy for this)

Or do you feel (as I do) that we should give them the opportunity to redeem themselves. Then neg the sh*t outa them if they screw up again?
Yup, I feel as you do. Let the community self-moderate them as well.