CORRECTION:
I may have been mistaken about that cookie setting in Safari. We had earlier encountered a similar problem as you'd described, where changing that setting seemed to solve the problem, but we just tested with another Mac also using that default setting in Safari, and any cart we tested there worked just fine for us, as did a fresh install of Safari for PC on my workstation here, just now.
In fact (and contrary to my previous understanding), our cart software can and does use the Merchant's own site URL to set and read the cookie (as our cart-button code effectively embeds our cart scripts into the Merchant's own page), so that would still count as a cookie set by a site to which the user had navigated, which that default cookie policy would allow.
While changing that cookie policy seemed to fix the problem, the fix may actually have been something else related to changing that policy -- maybe Safari deletes or resets cookies in the background, or rebuilds its cookie database, whenever you change the cookie policy? We now think the problem you were encountering was due to a bad/cached cart cookie that was somehow conflicting or not allowing new cart cookies to be set, or perhaps it was some strange bug with the version of Safari you were using (which version our staffer's Mac also just happened to be using, last time we'd tested), which has since been fixed by a subsequent update to Safari?
Just out of curiosity, could you tell us which version of Safari you were using?
