The easiest way to remove those photos is going to Maintenance -> Display videos and images not on disk, then you will see all the photos that can't be found in the location KPhotoAlbum expects them. You can then remove those from the database.
