Phil,
It's the "skimming" surfaces that Michael describes that is giving you heat.... Here's a video where I adjust some curves and cut your part.



So in the video you see me "raise the bottom curve" by a very slight amount, so it's not barely skimming through the entire bottom of the chair. The vertical curve is adjusted but you cant see it in the video. I used my "super nudge" command which moves .01mm. So I moved that vertical curve .04mm deeper into the solid to get a clean cut....

"""""""""""" I don't know if I should have approached this differently..."""""""""""""""

What you can do in the future, is model the veronoi with the base "much deeper, or thicker", then in this Boolean operation, cut the back to specs with your curve. Booleans are good to have a "complete intersection".............