The best solution I've been able to come up with on my own involves Harry breaking the compact between the dementors and the ministry:
"I am not yet done!
Lucius, while I appreciate you desire for vengeance, pointing it at the wrong target gains you nothing. However, it does inconvenience me. Hermione Granger is mine. I have claimed her, and I will have her, healthy and with her magical abilities intact.
Dementor! The compact you have made with the Ministry has been broken. I have already begun teaching the charm which was used to destroy one of your kind at Hogwarts earlier this year. You will return immediately to Azkaban and tell the other dementors to leave that place. Should any of you wish to side with the ministry, be certain that we will destroy you all. Go, now."
[dementor leaves]
"We are now at war. The spell to destroy dementors does in fact exist, a fact Albus Dumbledoor will verify. However, it is powerful, and can only be cast by very few wizards, wizards of a particular mind. Those who learn of it and fail will be permanently robbed of their patronus.
Hermione is one of the few wizards who can learn to cast the spell, and we all need her with her magical abilities intact.
Lucius, I may also need Draco, should he choose to side with me. As he is my friend, I will find who is responsible for this attempt on his life regardless of what has happened here today. As you have shown such devotion to him, I will not withhold anything I find from you.
I expect Miss Granger to be freed and returned to Hogwarts within the hour.
Professor, let us return."
This puts Harry in a position of power, where only he and his select crowd can destroy the dementors, with sufficient proof for the wizengamot to believe him. Breaking the deal between the dementors and the ministry drains Azkaban of its potency for punishing Hermione, and house Potter has claimed Hermione; but Harry has also offered to house Malfoy the dual olive branches of an unconditional offer to find the real perpetrator, and elevating Draco to a protected position of power in Harry's future hierarchy, which clearly does not involve the Ministry.
Should Lucius press Hermione to Azkaban regardless, it would be a hollow victory and serve only to piss off Harry. Harry has already demonstrated stronger control over the dementors than the Ministry, and can simply elect to send them to Malfoy Manor if he is sufficiently irritated.
The only down side is that I don't see a really good political escape for Lucius. There are a handful of minor ones that Lucius could use, for example his Imperius debt:
"In deference to the Noble House Potter and the blood debt owed it by House Malfoy, I rescind the order sentencing Miss Granger to Azkaban. I trust Lord Potter and my son to ensure that her debt is paid in full. I propose we remand Miss Granger to Hogwarts and discuss this more serious matter of the dementors."
Your plan basically relies on stripping your country of one of its most powerful weapons and then having the leaders of your country thank you for it. Good freaking luck.
EDIT: New discussion thread here.
This is a new thread to discuss Eliezer Yudkowsky's Harry Potter and the Methods of Rationality and anything related to it. With two chapters recently the previous thread has very quickly reached 500 comments. The latest chapter as of 17th March 2012 is Ch. 79.
There is now a site dedicated to the story at hpmor.com, which is now the place to go to find the authors notes and all sorts of other goodies. AdeleneDawner has kept an archive of Author's Notes. (This goes up to the notes for chapter 76, and is now not updating. The authors notes from chapter 77 onwards are on hpmor.com.)
The first 5 discussion threads are on the main page under the harry_potter tag. Threads 6 and on (including this one) are in the discussion section using its separate tag system. Also: one, two, three, four, five, six, seven, eight, nine, ten.
As a reminder, it's often useful to start your comment by indicating which chapter you are commenting on.
Spoiler Warning: this thread is full of spoilers. With few exceptions, spoilers for MOR and canon are fair game to post, without warning or rot13. More specifically: