How to prevent cookieless URLs?

Question

As far as I know, I have disabled cookieless URLs in all places in web.config:

<system.web>
  <sessionState cookieless="UseCookies" />
  <authentication mode="Forms">
    <forms cookieless="UseCookies" loginUrl="~/loggain" timeout="2880" />
  </authentication>
  <anonymousIdentification enabled="false" cookieless="UseCookies" />
<system.web>

I still get the cookieless URLs from time to time, browsing our site. the path can look something like this: /(F(5wpzvCsOC[...snip...]9NXal01))/About/

The problem is that some of our URLs include product names that can be very long which results in a HttpException with "the length of the URL [...] exceeds the [...] maxUrlLength". Also Google seems to index these URLs, but I've added link canonical to try to avoid this.

It's an ASP.NET MVC 3 site running on IIS7.5, if that matters.

EDIT: I've had this problem put on the shelf for a while, but today it occurred to me that it could have something to do with caching. I cache some child actions to speed things up a bit, but if the request that gets cached contains the (F([stuff])), the cache naturally(?) contains these links. The question now is if I can prevent ASP.NET MVCs Html.ActionLink() from generating these links in the first place?

Brunn

Does it still happen after clearing your browser cache, particularly, clearing your history? – Ashbaugh

To me it seems completely random when (or if) I get these URLs. I've cleared everything in the browser and when browsing the site all of a sudden I get these cookieless URLs. – Brunn

Are you in a load balanced environment, could there be a server that's still not had its web.config updated? – Ashbaugh