I have managed to restore some of the VMs to replication but I think this is to do with how they were deleted. The replication was stopped from the wrong end or the machines were deleted before being removed from replication or something.
I need to find where the replication partner is remembering the VM IDs.