"Add to Cart" redirecting to page not found

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.

This is not a proper fix, but resolved for me until I find a better fix.
At line 22 of the file init_sanitize.php I paste the following:

$link = HTTP_SERVER . $_SERVER['REQUEST_URI'];
	if (ENABLE_SSL == 'true')
		$link = HTTPS_SERVER . $_SERVER['REQUEST_URI'];

	zen_redirect($link);

This will redirect the user to the same page if a security token is not found.

EDIT: the above fix will make your IPN notifications fail.
So I don't recommend using it.

diego.s.v:

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
Perhaps there's a deeper issue at stake here, such as your store isn't properly starting sessions, thus the addition of the zenid to the URL.
THAT would be a smarter place to focus your attention.

And especially since Zen Cart doesn't generate URLs that end in ?zenid=xxxx (namely the question-mark is the giveaway here). You're using some sort of alteration to the URL generation, probably a so-called "SEO" addon of some sort.
Perhaps turning off all that other stuff and going back to the basic working Zen Cart code would be a good troubleshooting step. If there's still a problem there, when nothings being tampered with by custom code and .htaccess rules, then sorting out session problems in your configuration and/or your hosting would yield the most valuable and efficient results.