It looks like the “shifting trick” is really working:
The slightly “lighter” rectangle at the bottom is an example of the above “case 3”: That rectangle is fully located inside a triangle of the input triangulated surface, so it looks like “case 1” is at least “almost solved” now.
Note: So far, I did not realize the “back shifting” of the shifted points. (Maybe a “clean polydata” would be required afterwards!?)