I had this issue on Hardy Heron and like you, I have tried lots of workarounds without success. When I installed Jaunty (I'm on 32bit), the problem went away.
Yesterday I have tried Karmic alpha, but decided to go back to Jaunty. For my surprise, the video tearing was back, even after re-installing all previous installed applications and libraries. Additionally, I didn't change any settings, since I have a separate home and I have restored any changes to configuration files outside home, like xorg.conf for example.
Anyway, I figured out the problem. There is a bug in the nVidia driver related to permissions, that removes the direct rendering settings from xorg anytime I start nVidia settings.
If I run the code below, it tells direct rendering is off, unless I run it with sudo:
So after some research, I found this bug report, which also provides a fix.
glxinfo | grep -i direct
Basically, I had to edit /etc/rc.local
and add the following before "exit 0":
gksudo gedit /etc/rc.local
Works like a charm now. No tearing at all. I hope this helps.
chmod 666 /dev/nvidia* &