The first time it was on Jetpack ROM v8.2 JW1 (I can't recall which kernel, because I tested a few), but now it happened again on the Surface v9.0 JVU ROM with semaphore 2.5.0 kernel.
It's definitely not this issue: http://code.google.com/p/android/issues/detail?id=3692, because no jpg file was affected and there was no .nomedia file in these directories. Even the videos from /external_sd/DCIM/camera were deleted!
It seems it's a Media Scanner issue. Has anyone encountered this issue?
I found the culprit!!! It seems that the "innocent" Vovio Vitamio Media Player has a bug that deletes all videos!!!! DO NOT INSTALL IT until they provide a fix (they are aware of this problem).