Along with cookie encryption, you should also implement a rotating token to prevent replay attacks.
The idea being that the encrypted cookie contains some value which can be compared to a known value on the server. If the data matches, then the request succeeds. If the data doesn't match then you are experiencing a replay attack and need to kill the session.
UPDATE
One of the comments asked if I meant to store the value in the cookie. The answer is yes. The ENTIRE cookie should be encrypted, which can be automatically done through the use of an HttpModule. Inside the encrypted cookie is any of your normal information + the changing token.
On each post back, check the token. If it's valid, allow the transaction, create a new random token, store in the cookie, and send that back to the browser. Again, in an encrypted form.
The result is that your cookie is secure (you are using 3DES?) and any attacker would have an extremely limited window of opportunity to even attempt a replay attack. If a token didn't pass muster, you could simply sound the alarm and take appropriate measures.
All that's needed server side is to keep track of the user and their current token. Which is usually a much smaller db hit than having to look up little things like the users name on each page load.
UPDATE 2
I've been trying to figure out whether this is better or worse than keeping the changing value stored in session. The conclusion I've come to is that storing a rotating value in session on the web server does absolutely nothing to prevent replay attacks and is therefore less secure than putting that value in a cookie.
Consider this scenario. Browser makes request. Server looks at the session id and pulls up the session objects, work is then performed, and the response is sent back to the browser. In the meantime, BlackHat Bob recorded the transaction.
Bob then sends the exact same request (including session id) to the server. At this point there is absolutely no way for the server to know that this is a request from an attacker. You can't use IP as those might change due to proxy use, you can't use browser fingerprinting as all of that information would have been recorded in the initial exchange. Also, given that sessions are usually good for at least 30 minutes and sometimes much longer, the attacker has a pretty good sized window to work in.
So, no matter what, to prevent replay you have to send a changing token to the browser after each request.
Now this leaves us with the question about whether to also store values such as the user id in an encrypted cookie or store it server side in a session variable. With session you have concerns such as higher memory and cpu utilization as well as potential issues with load balancing etc. With cookies you have some amount of data that is less than 4kb, and, properly done, in the 1kb or less range that gets added to each request. I guess it will boil down to whether you would rather add more / larger servers and internal networking equipment to handle the requests (session) or pay for a slightly larger internet pipe (cookie).