Martin O'Neill must be pulling his hair out wondering how his side failed to take something from a game that they dominated.
And this after they battered Newcastle from pillar to post despite being 2-0 down to goals from James Milner and Kieron Dyer in the opening seven minutes.
Villa had both their new signings - Ashley Young and John Carew - in their starting line-up, while United new boy Oguchi Onyewu was watching from the stands.
The USA international will instead make his debut at Fulham on Saturday, against a club that was keen to sign the central defender.
Young pulled back a first-half goal in an outstanding debut and was matched by Carew, who did everything but score including see a thunderous header hit an upright.
Then despite being under the cosh, United broke for Antoine Sibierski to stick away his seventh of the season in time added on to snatch the most unlikely of 3-1 wins.
Worryingly for Villa, they have now managed just one win in their last 14 games.
Damien Duff returned to make his first United start in 17 games with Titus Bramble also returning after missing the last 14 games.
Villa were stunned when finding themselves two down inside the first seven minutes.
Milner, who spent last season at Villa Park, started the ball rolling with a stunning goal after five minutes, meaning he has scored in each of United's last four home games.
Cutting in from the right, Milner slipped several defenders before lashing a drive high into the net, though Thomas Sorensen will have to ask questions of himself on how the ball got beyond him.
Within 60 seconds that score was doubled, when a Milner corner was returned him and he turned from scorer to provider.
The winger spotted Dyer unmarked and the cross to perfection saw the England man nod in a rare headed goal.
It could have got even worse for Villa after 16 minutes when Scott Parker just inside the Villa half, worked a one-two with Dyer to fire over Sorensen and against the bar.
A third goal would have finished off Villa. Instead, they stepped up a gear and pulled back a goal after 25 minutes. Parker got the ball off the line only to see Paul Huntington clear straight to Young, who rifled the ball beyond Steve Harper.
That goal saw Villa take total control of the rest of the first half. Young saw an overhead kick fly over then, Carew crashed a header against a post and saw Harper somehow keep out a close-range volley.
In the opening seconds of the second half Dutchman Wilfred Bouma played in a great ball from the left that saw Gabriel Agbonlahor outjump Huntington and force an excellent save from Harper.
It was almost a non-stop claret and blue tidal wave towards the Newcastle goal as the home side struggled for possession.
Carew led the home defence a merry dance along with Young and O'Neill looks to have hit the jackpot with his two new boys.
But try as they might, Villa could not force the equaliser that they at the least deserved and they then lost their way when Carew limped off after 69 minutes.
And it was Newcastle who wrapped up the points in time added on when Obafemi Martins and Duff combined for the latter to tee up substitute Sibierski to beat Sorensen at his near post.