APM, a long-standing combatant in my battle against my own misunderstanding, has responded to my first salvo.
First your question of why the feeling of free will should arise through evolution. Can we rule out the fact that our apparent 'free will' is a bonus from a more important evolutionary adaptation. I seem to remember discussing this with you at the end of a long pub visit some time ago. Speaking as a totally ignorant non-biologist, I could suggest that a key aid in survival is imagination, the ability to realise that rubbing the sticks together produces something more useful than splinters and that a sharpened stick is useful for both catching fish and despatching a competitor. Might it be that what we perceive as free will is actually just a consequence of a sophisticated ability to assess the environs and work through potential dangers, benefits and solutions. It might be argued that the broader ranging, or free-er the calulations the better benefit.
I like this idea. If I understand correctly, you're suggesting that the phenomenon that we perceive as free will is related to whatever mechanisms drive imagination. I guess that some "imagination subroutine" generates ideas, presumably by sifting and combining memories, then somehow evaluates them (a "simulation subroutine"?), before culling them down to the "best idea". And that, since it involves selection and "choice", this process has an associated emergent phenomenon that we perceive as free will. In this way, a reasonable connection can be drawn between a deterministic algorithm for selecting novel behaviour, and the associated specific perception of free will.
While I can see the connection that you've drawn out there, I'm still hazy on whether it necessitates such feelings of freedom. But it could go some of the way to explaining why certain deterministic processes have very particular emergent phenomena associated with them. I do still find it hard to swallow that even such goal-oriented processes would generate a non-interactive perception of such specificity that cannot feedback onto them. But that's the rub I guess.
If I can get all metaphorical about it for a moment, how's about this: In the conventional view, the cogs and wheels of strict materialism manifest themselves both as external behaviour (i.e. I have a cup of tea) and a perceptual "projection" (i.e. I experience myself having a cup of tea). But this latter part is coupled one-way and does not feedback on the cogs and wheels. In my non-conventional (and possibly deviant, quasi-dualist) view, the cogs and wheels of strict materialism manifest themselves in the same way, but the perceptual "projection" is somehow (and this is a huge "somehow") coupled two-way. Now, since in the former case the "projection" is solely an output, it's not obvious to me that evolution would shape it to such high precision. But if it somehow feeds back onto material events, then it's easy to see evolution making it as focused and accurate as our perceptions are.
In this sense, much as with my misguided take on quantum mechanics, I guess I'm arguing that my conception of free will relies on a form of hidden (at this time) variables. I don't doubt that a (large?) part of behaviour in all animals operates at a sub-free-will level, for instance reflex actions. But part of my subjective experience suggests that there's more to it than this, and that aspects of perception that are essentially coercive (pain, pleasure) don't make a lot of sense if the coercion is only operating on something that cannot respond to it. Admittedly, there's still the possibility that what we perceive as pain and pleasure is merely an outcome of deterministic feedback loops in our heads, but my objection to this is that they're pretty refined for things that, essentially, don't do anything.
My hunch is that evolution, through the production of deterministic brains that process information into detailed representations of the real world, has somehow accessed hidden variables that currently lie outside our understanding of the material universe. These variables permit functionality beyond that attributable to atoms and electrons. But having just written that, it sounds like a load of old tosh and the road to mysticism to me.
This leads on to another of your points, regarding why we might have developed pain and pleasure sensations. This seems to be assuming that our conscious is outside our biological entity. If our consciousness is just a rather sophisticated computer then it is no surprise that we are aware of our senses relaying important information to it as it has clearly been developed to take a longer view than a simple reflex action.
Be gone Dualist Demons! ;-) Yes, I suppose that I am arguing for a more complicated relationship between matter and mind. Part of the problem in all of this is that I don't believe we have any good ideas about what consciousness is "made" of. It isn't obviously made of atoms, nor is it anything that seems attributable to the various force fields that pervade us. It clearly isn't "contained" within a single "master neuron", but if it's a distributed phenomenon, what substrate is it spread across? That said, it's also obvious from a wide range of evidence that, whatever it is, it's intimately related to the organic material between our ears. Such that, among other things, injuries in specific areas affect it in predictable and catastrophic manners.
However, if we assume that consciousness isn't free (i.e. two-way interactive), and that it simply represents the working out of conventional deterministic processes, I don't think it follows that it's "no surprise" that it contains such well-honed perceptions such as those provided by our senses. A one-way connection between neural physiology and consciousness would effectively make the latter invisible to evolution. But I appreciate that sentence does take something of a dualist perspective on the nature of consciousness!
Finally, just to clarify something, I'm uneasy with the argument that we don't know all of physics yet so there might be another explanation for free will as it seems to dodge the question. Your comment on it being extremely unlikely to have arisen by coincidence sails a little too close to concerns over the evolution of the eye too perhaps?
It's a fair cop. Falling back on as-yet-unknown physics is a weak argument. But I do think (possibly erroneously) that our perceptions lie outside of what we currently know about physics. And I don't just mean that we haven't ironed out the details, I mean that there does not yet appear to be anything like a clear mapping from the observable quantities of physics (particles, waves) to what goes on in our heads. Putting it flippantly: what is my pain (pleasure/love/hate/joy/fear) made from? I don't doubt that it's made from something material, but I don't think that we have a good handle on quite what yet.
Re: Eye evolution, I do hope you're not suggesting I've gone over to the Dark Side! ;-) Actually, re-reading the above, I do sound a bit like some counter-revolutionary dualist. Time, perhaps, to stop digging ...
 When I say "deterministic" here, I don't mean to exclude stochastic processes. I really just mean processes whose outcomes are not guided by anything that science is unaware of (if I can double-negative myself). Either ones that are completely deterministically driven by past events and a system's state, or those which are completely stochastic and independent of history or the current state of the system. Basically, not "free will" which, as conventionally understood, is some kind of additional "quintessence" that can independently (i.e. non-deterministic) and purposefully (i.e. non-stochastic) drive a system.
 In fact, since we have no good idea where this "projection" is, or even what it's "made" of, there are reasons to get suspicious of this picture from the get-go, but I don't want to get back into that for now. Not least because I don't have any good ideas about this either.