As I often transfer the photos from my (Android) phone to the PC, I delete them from the phone. However, the thumbnails remain in the Gallery application. They happen to be black, indicating there is no photo, but they are still there, which is a bit annoying. I tried some tips from forums to use Astro to clear thumbnail cache but that did not help.
To remove all the thumbnail data - go to Android directory on the phone (on Android 2.3.7 Cyanogen it is on SD Card in /mnt/sdcard/Android). Delete "com.cooliris.media" directory.
After this, you will notice the media manager rescanning the media and, when you open the Gallery, only the existing photos will have thumbnairs. Voila!