Any creature equipped with Stitcher's Graft must be sacrificed when it's no longer attached. My question is do you sacrifice the creature exiled by a spell such as Cloudshift or will it just come back good as new?
As rule 400.7 explains, the exiled creature is a new object:
An object that moves from one zone to another becomes a new object with no memory of, or relation to, its previous existence.
Stitcher's Graft's third ability mentions "that permanent", which does not exist anymore, so it cannot be sacrificed.