Surrogate it is clear that the issue is indeed formulas in the document's shapesheet that shape cells are referring to, but this time the issue is with a twist.
Somehow between the current document that has been extensively changed and the current stencil that has been extensively changed (meaning user section cells have been added and removed and changed their contents several times as shapes were developed), something between the document and the stencil is mismatching.
If I move the shapes either in to a clean document or in to a clean stencil (just one of them), the issue just disappears. In this case Visio seems to be holding on to old information about the shapes and the documents, as the user section cells that were the problem were removed (and the references in the shape cells to them were removed as well of course), yet in the old document and stencil the issue cannot be resolved. Some old information seems to be sticking around, in the document stencil masters maybe? (I have not edited document stencil masters directly, but I have dragged in updated masters from the stencil frequently).
Only when either a fresh new stencil and/or document is used, Error 318 disappears.