What made the Ministry admit Sirius was innocent?

Question

In Prisoner of Azkaban, Professor Dumbledore explains to Harry why he cannot convince the ministry that Sirius is innocent. Yet, in the beginning of Half-Blood Prince, the Minister of Magic admits to the Muggle Prime Minister that Sirius Black was innocent:

‘Is Serious Black with – er – He Who Must Not Be Named?’

‘Black? Black?’ said Fudge distractedly, turning his bowler rapidly in his fingers. ‘Sirius Black, you mean? Merlin's beard, no. Black's dead. Turns out we were – er – mistaken about Black. He was innocent after all. And he wasn't in league with He Who Must Not Be Named either. […]’

– The Half-Blood Prince Chapter 1: The Other Minister

What has changed that has made them admit his innocence?

Sirius's body disappears in the fight in Order of the Phoenix, so there's no evidence left that he has fought there. Pettigrew is still in hiding. There's still only Harry and Hermione's word against Snape's story that would prove Sirius's innocence.

Answer 1

Presumably it was right after Voldemort fled from the Ministry at the end of book five, when Dumbledore was telling Fudge everything that happened:

"You will give the order to remove Dolores Umbridge from Hogwarts," said Dumbledore. "You will tell your Aurors to stop searching for my Care of Magical Creatures teacher so that he can return to work. I will give you ..." Dumbledore pulled a watch with twelve hands from his pocket and glanced at it "... half an hour of my time tonight, in which I think we shall be more than able to cover the important points of what has happened here. After that, I shall need to return to my school."
_{The Order of the Phoenix Chapter 36: The Only One He Ever Feared}

As part of the important points of what happened, Dumbledore would certainly have mentioned that Sirius died and, through his infinite credibility at the time, would probably have convinced everyone there of Sirius' innocence.

It's rather difficult to deny Dumbledore's word moments after he's fought against Voldemort.

Answer 2

Harry (and by implication Dumbledore) has been proven to having been truthful, now that Voldemort showed up at the Ministry in the end of OoTP.

This makes Harry from a "lying because the Ministry said so" to "Was right all along and Ministry effed up". So, naturally, the OTHER story where Harry disagreed with the Ministry is now judged to have been true as well.

Answer 3

I don't actually think you can produce a quote to prove that the Ministry ever did admit in public that Sirius Black was innocent.

Sirius "proved" his innocence of the charges against him (which were, basically, of having been a supporter of the Dark Lord and of killing people on his behalf) by getting himself killed in the fight against Voldemort.

Prior to that, the Minister - Cornelius Fudge - was reluctant to admit that Sirius was innocent; but had to accept that he was once Sirius had died at the hands of the Death Eaters (in Order of the Phoenix) -- and in the Ministry's own basement, in front of witnesses.

But Fudge always maintained that Sirius was guilty, so long as he was alive. Only when he was safely dead did Fudge change his position, to a cautious acceptance of his innocence, at least in private (to the muggle Prime Minister in The Half Blood Prince). But by then he was no longer Minister for Magic: the Ministry's public position was now being decided by his successor. And it would have been far easier for Rufus Scrimgeour, the new incumbent, to announce that Sirius was innocent and his conviction a mistake, as it was a mistake made by someone else, i.e. by Fudge.

It was a nice touch to give the Minister for Magic the name Fudge, since it summed up his character so neatly: like all politicians, he fudged every decision that needed making, and he fudged rather than make any decision at all. In his treatment of Sirius Black he followed those principles admirably.