If a program deletes an original image and knows about the thumbnail mechanism it must delete the thumbnail too. This doesn't solve the problem for images which are deleted eg. from the commandline. For these the solution is to check regulary (or by user demand) if all thumbnails have corresponding original images yet. If not they can be safely deleted.
For thumbnails of remote originals which are saved in ~/.thumbnails/'size'/http:/ or ~/.thumbnails/'size'/ftp:/ there should be all deleted which aren't accessed within the last 8 weeks.