Same issue here.
What I've found so far is:
1. at line 19 of /includes/init_includes/init_sanitize.php there is a check if the $_SESSION['securityToken'] exists, if not, create one at line 21.
- Test: Cleanup your browser cache, comment line 21 of init_sanitize.php and load a products page. Look at the HTML source code and you'll notice that the "securityToken" hidden field is blank.
Do not browse for the product, go to directly to the product's page.

2. when the page is loaded the init_sanitize.php creates a $_SESSION['securityToken'] because it doesn't exists
3. when you try to add the product to your cart, you get a page not found, because at line 116 of /includes/functions/sessions.php there is another check for $_SESSION['securityToken'] - Seems that the first init_sanitize.php assignment of $_SESSION['securityToken'] is not working

I'm using "Force Cookie Use" set to "True" - when changing to "False" everything works, but I get that ugly ?zenid=XXXXXXXXXXXXXXXXXX to my URL

If you load the product's page twice, you don't face that issue. This only happens if someone that never visited your store comes right to your products page instead of browsing your categories for example.