"Isn't there a story where the Buddha accosts a monk who's bleeding from performing walking meditation for too long, and tells him practice must be like a Veena's string - not too tight, not too loose? i.e the middle way"
The string story is in AN 6.55.
"Yet, I remember a story in the Dhammapada (Verse 1) about a monk who refused to take his eye medicine because he had vowed to not lie down for three months and remain practicing full time. Since the medicine wasn't effective unless taken lying down, he lost his eyes.
The text says he simultaneously lost his vision and gained his vision - i.e. he became an arahant by practicing so arduously."
It seems this story is not described in Dhammapada, but in a commentary? I could not find a full text of it.
"The Buddha peeks into his past lives, and says Karma dictates that he must lose his eyes in this lifetime for sins of the past."
I've never found this kind of wording in any sutta: "karma dictates" or "because of karma, he must". Describing karma in this way is not only at odds with the actual karma doctrine taught by the Buddha, but he also criticized the idea that "karma dictates": it would be impossible to anyone to live the holy life, become an arahant, become a Buddha, if that was the case.
"Leaving everything to Karma has me confused - because if that is so, then why practice, even enlightenment if it is in our karma will be obtained without effort. Gautama the Buddha was certainly going to become a Buddha, his Buddhahood had been foretold, so why did he practice?"
The questioning above is similar to the way the Buddha often debunked this very idea.
"Monks, for anyone who says, 'In whatever way a person makes kamma, that is how it is experienced,' there is no living of the holy life, there is no opportunity for the right ending of stress. But for anyone who says, 'When a person makes kamma to be felt in such & such a way, that is how its result is experienced,' there is the living of the holy life, there is the opportunity for the right ending of stress.
-- AN 3.99
A book I would suggest here is Good, Evil and Beyond: Kamma in the Buddha's Teaching (besides the suttas where karma law is taught).
"Second, what's with the open praise of macho effort right at the start of the Dhammapada? What happened to the middle way?"
It's less about macho, and more about determination.
Also "middle way" does not mean avoiding anything one may personally consider to be "extreme". When this denomination is used by the Buddha, he is either talking about avoiding specific sterile and false/incorrect extremes:
"There are these two extremes that are not to be indulged in by one who has gone forth. Which two? That which is devoted to sensual pleasure with reference to sensual objects: base, vulgar, common, ignoble, unprofitable; and that which is devoted to self-affliction: painful, ignoble, unprofitable. Avoiding both of these extremes, the middle way realized by the Tathagata — producing vision, producing knowledge — leads to calm, to direct knowledge, to self-awakening, to Unbinding.
-- SN 56.11
...or explaining how this is his strategy of teaching:
"'Everything exists': That is one extreme. 'Everything doesn't exist': That is a second extreme. Avoiding these two extremes, the Tathagata teaches the Dhamma via the middle: : From ignorance as a requisite condition come fabrications ...
-- SN 12.15
"This is not an isolated instance, there are several stories about heroic efforts from monks. The most famous must be the version where Bodhidharma plucks out his eyelids. There's also another version where he loses his legs to atrophy by not moving for nine years."
Though Zen has the habit of increasing the dramatic effects a noch, still, it's how determination is conveyed. Underlying this intense determination is a sense of urgency, often produced by an experience of insight into the dhamma.
So, it's not about heroism -- not in the western sense. Nor about sacrifices. The kind of sacrifices praised by the Buddha are sacrifices of unwholesome acts of body speech and mind. Are sacrifices related to the household life, and so on.
It was pointed out that physical pain may significantly affect one's mind in a karmic way. But mostly as an explanation of the law of karma, not as a practice to be undertaken -- that is, to inflict pain in oneself. (I don't remember the sutta, unfortunately; it's a passage where the Buddha says someone who undergoes a lot of pain may find him/her self reappearing in a better realm because of that).
"I got to thinking about this after reading this question about monks and exercise. I am reminded of "A path with heart", by Jack Kornfield, where the author, himself a Buddhist monk under Ajahn Chah for several years talks about exercise and several other normal healthy things monks ignore in order to pursue enlightenment single mindedly. He recounts interviewing several monks who suffered from diabetes and other lifestyle diseases that came from not eating healthy food, from not exercising, from developing an aversion to their body and consequently not caring enough."
As far as their body negligence, from the point of view of Buddhism (and of the path to Nirvana) these monks are blameless or not depending on their intention. The bodily pain (or what one could see as a "sacrifice") produced by these health disorders alone is not necessarily praiseworthy or blameworthy -- though it could present itself as an obstacle which could have been avoided. Finally, their suffering depends on their skill and maturity.