On some machine it seems like randomly the journaling is lost and the
backup has to go through the whole harddrive again. This takes hours
instead of the usual minutes, there seems to occur completely at random.

Any suggestions?