For those of you having problems with VPU Recover errors with a brand new Radeon 9600XT (and the future me, the next time I reinstall), this page has the solution to all your problems. Turning off AGP Fast Writes and flashing my BIOS worked for me.

Update 20 Feb 2006: After getting a new motherboard and updating all of my firmware and drivers, I started having problems again. I found this page and tried some of the things on it. Setting AGP to 4x, in particular, seemed to help a lot.