I have the same problem windows vista,7 rebuild thumbnails(maybe don't rebuild,simply overflow cache, this leads to the reconstruction of cache thumbnails, becose the file thumbnails increase in mb) don't work for me,but if you try increase pagefile.sys, yuo cache support more thumbnails.
an alternative is try thumbsplus7(works very vell) but isn't free.
an option try edit regedit, delete *.avi,*.jpg if you only works with *.mp4
i hope useful for you.
note:sorry for me english,I do my best .
not enough but at least try