We use Piwik with the cookies disabled: use_third_party_id_cookie = 0 and _paq.push(['disableCookies']); (trying not to have to display those stupid EU-warnings about Cookies).

Unfortunately it seems the case that there is some mixup. If "do not track" is disabled in the browser everything is fine, if it is enabled a Cookie is set.
I think the idea of this cookie is to "delete" cookies that might have been set before, as the expiration is before the cookie is actually set. If this is the case, the correspoding page in the FAQ should probably be updated to include this.

Piwik version is 2.16.1.