Yeah - I don't disagree that there isn't possibly some level of risk. But if your concern is "GoogleBot figuring out that I'm not really cloaking" based on the presence of cookies then I'd challenge (what I think is) your implication that having cookies on your site means Googlebot might suspect you of crawling.
As to Googlebot's use of cookies - there is debate and folklore, but in the tests I have run I have not seen Googlebot ever send back a cookie that I have sent it.
Google do manual reviews of pages, and I am confident the site in this example (for the case in question, at least) would pass that without a problem.
I'm (genuinely) interested in your proposed solution for dealing with the duplicate content problem. The problem with the Panda algorithm is tends to be a bit touchy and it seems easy to fall foul of it even with innocent situations like this one.