Jume

then i think we got it right, it may be the video codec not responding when
generating the thumbnails

just to be sure:
in control panel / personalization / folder options / "view" tab / scroll
down the list until you find something like "show always icons, never
thumbnails" and check it, accept the dialog to close it
this way, the thumbnail generation will not be called then the video will
probably get deleted fine

if this little experiment is successful, then, if you know the video codec
used, try looking for a vista compatible version which may correct this
issue
if you dont know which codec, just tell it and we'll try to guide you to
find it

on a sidenote, i myself use something called ffdshow-tryout without troubles
in vista x86, not a codec pack but 1 able to play almost anything, if you
have a 32 bits vista version and you have a codec pack installed, you may
want to try alternatives like this to solve the problem