This is due to dual-booting with an earlier version of Windows which does not recognise the restore point format and deletes it (!). In my case I was dual-booting Windows 8.1 with Windows XP but other combinations are possible.
This issue can be worked around by disabling mounting of the newer operating system's disk/partition from the older operating system by setting the registry key:
HKEY_LOCAL_MACHINE\SYSTEM\MountedDevices\Offline REG_DWORD "\DosDevices\D:" -> 1
D: is the name/mount point of the newer disk/partition when running the older operating system. You can obviously no longer access the new disk from the old operating system in this case but could do so through a third disk/partition or other media. The new operating system is still able to access the old disk/partition.
Full information in the knowledge base article. It also mentions working around this problem using disk encryption.