Milner was three months into a season-long loan from Newcastle when David O'Leary took a near full-strength side to Belle Vue for what should have been regulation passage into the fifth round. That was the plan anyway.
Their League One hosts had other, far grander, ideas of their own. And, after an early penalty from Michael McIndoe, they never surrendered their advantage, sealing a memorable win with further second-half goals from Paul Heffernan and Sean Thornton.
So what went wrong?
"Who knows?," Milner shrugged. "A cold night away at Doncaster? Some may have got off the coach and not felt too good about it. It was just one of those nights.
"We definitely want to put it right this weekend."
One major change is that Saturday's FA Cup fourth round rematchwill not be at ramshackle Belle Vue, but at the 15,000-capacity Keepmoat Stadium, Rovers' home of the past two seasons.
But Milner's bullish tone ahead of Villa's return to South Yorkshire is understandable.
With three goals in as many games (including both in the win at Gillingham in the last round), the club's record signing is starting to show why Martin O'Neill shelled out a reported£12m to ensure he moved Parks - from St James' to Villa - during the summer.
Milner is a better player now and Villa are a better team.
Back in 2005, under David O'Leary, there was talk of woeful underachievement and a real threat of relegation. Now there's chatter of the Champions League. Everyone has come a long way in three years.
"It'll be completely different with our current form and we'll be going there full of confidence," said Milner. "We have to make sure it doesn't happen again."
Progress in cup competitions depends on a whole host of things - luck, attitude, commitment, the weather and, of course, tremendous focus.
And had Villa had a touch more of that last factor when they played out an FA Cup saga with Doncaster in 1955, they may have got to Wembley a couple of years before they last won the trophy in 1957.
Peter McParland hit the goals as Villa beat Man Utd 2-1 at Wembley in 1957
Their fourth round tie was an epic, running to a fourth replay before Doncaster eventually 3-1 at The Hawthorns.
Peter McParland, who scored both goals when Villa won the cup in '57, was part of the team then along with recently-mourned Villa heroes Johnny Dixon and Vic Crowe.
And he told BBC WM that Villa may have become distracted by a potentially romantic fifth round tie.
"The winners were to play Birmingham City and we were worked up to try and get through and have a great local derby.
"We played at Doncaster, Villa Park, Manchester, Sheffield, and West Brom. Five games in a short space of time. But it wasn't to be."
Villa return to Doncaster again this weekend determined to force a different destiny.