This is an interesting thread, because (a) I'm one of the 4% who won't accept 1st party cookies by default, and (b) my cart won't function correctly without my customer accepting that cookie.
I don't have any data on cookie acceptance, but 4% doesn't surprise me. These are probably potential customers who have a certain disdain for getting cookied-up the very instant they touch a web site. I question the impact of mobile phones; unless your widgets are geared toward that market.
I'm curious if you've done anything to accomodate non-robot visitors who refuse the cookie. Do you imbed a session ID into the URL? Are there any good alternatives besides issuing cookies to non-robot visitors?
Passing session IDs in URLs comes with a significant security risk - if someone else gets that URL, then they can pretend to be your user.
That means you have to be careful not to have session IDs showing up as referers, ensure that visitors don't pass around your links, etc. or come up with some method of checking that the session does actually belong to that person (and you can't easily use IP addresses, because of ISPs like AOL whose customers may hit different proxies on different page loads, and hence appear to have a different IP to your server.)