You're encoding AVI's to DVD? Toast will do that, or VisualHub.
As for the codecs, make sure to check:
/Library/QuickTime/ and ~/Library/QuickTime/
just to be sure you've gotten everything out of there except Perian (well, besides Perian, I've got AppleIntermediateCodec.component in my /Library/QuickTime/ folder, and AC3MovieImport.component in ~/Library/QuickTime/).
I do actually use Toast to burn dvds. I just check 'em quickly in Quicktime (to make sure i have all the correct codecs)
Fixed!!
I deleted all codecs again, and all other evidence of any related software. I think the problem was that i had 2 installer packages for DivX, and when i was re installing, it was only updating. Maybe this left some of the broken software. I dunno! It works now though