Where was the Roman Army in AD408?

[Flavivs Aetivs]

That's the one, although the reinforcements from Constantinople arrived in Panormus where they met up with the professional army.

"militum atque foederatorum"

Which translates, as you said, to "both soldiers and federates." I think this is an indication that at least some of these were professional soldiers. We know they existed as they're mentioned several times - Aetius' and Majorian's army at Vicus Helenae is explicitly stated as Roman, and the defendes of Aquileia are described as Roman Soldiers (assuming of course it is a snippet of Priscus, which is conjectural).

The 'garrisons' mentioned, like the 'soldiers' organised by Sigisvuld, would perhaps have been on the levy type soldiers used for local defence and simply called 'milites' in the ND.

As far as we can tell milites was just a way of naming a unit. There's no indication that these were "levies" for "local defense" and the overwhelming majority of them in the Notitia are listed as Limitanei regiments.

However, you have a point in that local levies were probably a big part of this sudden need to see to the defense of Italy, as the Variae of Cassiodorus record that local militia drove off a Vandal raid near Tarentum in 440, while Panormus was besieged (this siege was lifted upon Aetius' approach).

the successful restoration of the army

To be fair, there's no effective way to interpret that. It's clear manpower was a severe issue in the 5th century as Aetius was largely drawing his recruits from the upper Rhine Alemanni and of course his Alans.

I don't remember off the top of my head who calculates it (AHM Jones, I think) but he says that in order to maintain the Gallic and Italic armies it would require 4500 recruits a year, which evidently in an Empire with a population of 50 million between both halves was difficult to field.

This sounds very much to me like the regular army of the previous century had ceased to exist in Italy

But that's impossible for it not to have existed. Let's assume 10,000 Huns was the average they could field themselves (without all their Germanic federates, and this is consistent with recent research on the early medieval Hungarian plain). Then Felix in 427/428 must have had at least in the vicinity of 10,000 men to campaign against them with, while Aetius was with the Gallic field army which must have numbered in the vicinity of 25,000 men in order to confront the Aquitanian Goths (estimates come from The Goths by Peter Heather. Conversely, in 454 the Gepids and Amali Goths (future Ostrogoths) probably each could field around 10,000 to 20,000 men.) It's impossible to say what the Salian Franks could field but it seems to have been significant.

To be fair though, the only actual number for a barbarian force we have from this period is the Neccar River Burgundians who ambushed and slew the Huns of Octar, who could field 3000 men against the Huns. Later, 700 Alemanni pestering North Italy was enough to get Majorian appointed emperor.

The fact that Sidonius poetically contrasts magna agmina with palatiniis... turmae in his panegeyric on Majorian is also evidence that there was a field army in 454, which suddenly disappeared (presumably as a result of Aetius' assassination). It also shows the Scholae were still around (even if they weren't exactly much more than a parade unit at this point).

As for the Notitia, if you do the math and assume that the Spanish, British, and African units were all wiped out, then deduct the approximate losses from the loss of Revenue in 439, that still leaves on paper around 37,000 Limitanei and around 31,000 Comitatenses for Aetius.

(I assumed the average strength of a Numerus was 640 men and assumed units of milites were organized as Numeri, Equites were Cunei and that the Cuneus numbered 256 men like the Tarantiarchia, and that Pseudocomitatenses units were typically Legions as evidenced in the Theodosian Code. The final number came out to roughly 225,000 men, and I began subtracting from there).

We can't guess at actual strength or account for unrecorded losses, but evidence from the 3rd century suggests the average operational strength declined from about 90% (1st-2nd Century AD) to about 70%. Coello shows this (although he makes no conclusions about actual unit size).