safeRestart currently doesn't seem to wait for pipelines to end before issuing a restart; it only waits for a step to end. Unfortunately, after restart, Jenkins attempts to resume the build on the same slave. In our cases – slaves launched on-demand from Mesos – the same slave does not and will never exist again, resulting in pipeline failure.

JENKINS-51323 exists for this issue, however it is marked as a minor improvement. I would consider it a major bug, because with ephemeral slaves, every single pipeline will fail if a safeRestart is issued.