Very strange.
Could you give me some insight as to how it deleted a folder, e.g. did you try un-install Kazaa or what.
I presume the deleted folder is your My Videos folder inside My Documents. (what OS are you using - Win98 / WinXP)
Also do you remember the name of one of the videos that were in that folder because it might be worth running a search on your hard drive to see whether the directory could have been moved to some "arb" place.
If you can't find anything then it might be worth downloading a File Recovery program
http://www.file-recovery.net/download.htm
http://www.active-undelete.com/
Lets us know how you get along