Two of the three creatures you listed as being immune to the frightened condition have abilities that can give that condition to others, while none of the creatures listed as susceptible do.
It makes sense that creatures capable of frightening others would be impossible to frighten.
However, this does not account for the shadow.
After further examination, this pattern seems to hold true for all the undead in the SRD. Creatures with immunity to being frightened tend to have the ability to frighten, while those without never do.
There aren't many alchemical or low-magic items especially usefull against Undead. There are a few you should definitely consider:
First of all, Positoxins (Libris Mortis 74-75)
To a corporeal undead creature, a positoxin functions much like a poison, usually dealing initial and secondary ability damage or drain when the target fails a Fortitude save. The ability damage or drain
dealt by most positoxins can’t reduce an undead creature’s
ability score below 1.
Despite their normal immunity to damage or drain to physical ability scores (Str and Dex), undead are vulnerable to the ability damage or drain caused by positoxins.
They are quite expensive. Their prices range from mere 100 GP to 1 300 GP. These may be really useful against more powerful undead like liches or vampire spawns. There are 7 different positoxins.
Ravages (Book of Exalted Deeds 34-36)
Ravages function in a manner similar to poisons, dealing ability damage or even ability drain when the target is exposed to them through inhalation, injury, or ingestion, and additional damage or other effects 1 minute after the initial exposure.
Ravages and afflictions deal damage only to evil creatures. Any evil creature takes damage equal to that listed on either the Ravage Table or the Affliction Table, plus its Charisma bonus. An evil elemental or evil undead takes an extra 1 point of damage, and an evil outsider or an evil cleric of an evil deity takes an extra 2 points of damage. If more than one kind of damage is listed, the creature's Charisma modifier and additional damage are added to each kind of damage.
There are only 2 ravages, that might be useful for this case, as the rest is way too expensive.
Golden ice, 350 gp, Type: Injury, DC 14, Initial Damage: 1d4 Wis, Secondary Damage: 1d4 Int, 1d4 Wis
Unicorn blood , 500 gp, Type: Injury, DC 17, Initial Damage: 1d3 Str, Secondary Damage: 1d4 Str
Special items against undead.
Aspergillum (Forgotten Realms Campaign Setting, 95)
50 GP
Each contains a reservoir that can hold up to 3 pints (three flasks) of holy water. By shaking the aspergillum as a standard action, you can sprinkle one flask of holy water on a target within melee reach. This action is a ranged touch attack (which does not provoke an attack of opportunity).
Ghostoil (Libris Mortis, 73)
50GP
When applied to a weapon, ghostoil allows it to affect incorporeal creatures normally for the next 2 rounds. Applying ghostoil to a weapon of any size is a fullround action that provokes attacks of opportunity.
Gravebane (Arms and Equipment Guide 34)
50 GP
When opened (usually by throwing it on the ground), a flask of gravebane fills a 5-foot-square area with smoke. Undead cannot enter an area filled with gravebane smoke unless they succeed on a Will save (DC 10). Gravebane ordinarily lasts for 1 minute, although strong winds may decrease this duration.
Holy Water Sprinkler (Libris Mortis, 73)
62 GP
Any hit by the holy water sprinkler also affects the target as if it had been within the splash radius of a thrown flask of holy water (1 point of damage to undead creatures and evil outsiders for holy water). A full reservoir has eight uses.
Alternatively, the wielder can choose to release the entire
reservoir with a successful hit. Treat this as if the target had been hit directly by a flask of holy water, but subtract 1 point of damage for each use already dispensed from the reservoir (for instance, a reservoir only 5/8 full would deal 2d4–3 points of damage). There is no splash effect from such a hit.
Filling the reservoir is a standard action that provokes attacks
of opportunity.
Crucial potions and oils
Regenerate light wounds (Masters of the Wild)
50 GP
Regain 1 hp in the next 11 rounds. If the encounter finishes and you can wait a minute, it is a better alternative to cure light wounds, as the value is constant and bigger (11 vs. from 2 to 9). If you'd drink more than one, they prolong the duriation of healing, so drinking 2 potions will make you regain 1 hp for the next 22 rounds.
Hide from undead
50 GP
Undead without intelligence treat you as you have not existed. Definitely a must have.
Magic weapon
50 GP
This is crucial against vampires with damage reduction.
Other useful pieces of equipment
Antitoxin
Very useful against abilities like Ghoul's stench.
Anti Disease Tonic (Dragon #331, 32)
100 GP
Grants a +5 Alchemical bonus on the drinker’s saves vs. Disease for 1 day.
Some undead creatures may cause serious diseases. This item may be a lifesaver.
Healing salve (Tome and Blood, 72)
50 GP
Applying the salve is a full-round action. One dose cures 1d8 points of damage to a living creature.
An alternative to the Cure light wounds potion, that is usable in an antimagic field.
Potion belt (Forgotten Realms Campaign Setting, 96)
1 GP
Potion Belt: This sturdy leather belt similar to a bandoleer has pockets shaped to hold potion vials and is fitted with ties or flaps to keep the potions from falling out. It holds six potions. Retrieving a potion from a potion belt is a free action once per round.
Best Answer
Creatures of the type undead typically have Constitution as a nonability; the Monster Manual on Nonabilities says, "A creature with no Constitution cannot tire and thus can run indefinitely without tiring (unless the creature’s description says it cannot run)" (312). Undead creatures (including incorporeal undead creatures) can take the run action even while flying: "A creature can use the run action while flying, provided it flies in a straight line" (MM 312). Undead creatures are also immune to nonlethal damage, so such creatures can hustle forever without issue.
"Can undead armies just run around at twelve times the speed of normal armies?"
This DM wouldn't allow such massive speeds for undead ground forces. In my campaigns, difficult terrain and obstacles are fairly frequent in most wildernesses, and both impede the run action, which requires the creature travel unimpeded in an unobstructed straight line. While the ability to travel without rest essentially doubles (or possibly even trebles) an undead ground army's overland movement, I can't imagine the ability to flat-out run tirelessly being strategically valuable even in the most desolate of campaign settings; a wilderness will have bad footing and stuff in the way. Seriously, even Athas has rocks.
There's the possibility, I guess, of scouting the terrain beforehand, clearing away obstacles or even building roads, but then the undead army's (ahem) dead run to its next engagement is slowed instead by all that preparation. It would take extraordinary circumstances for me to view the land-bound undead army's ability to run forever as a broad, easily leveraged advantage over a traditional army rather than an interesting quirk.
However, an airborne army composed of allips, shadows, spectres, and wraiths can certainly tirelessly run while flying, traveling quadruple (or eight times or twelve times) its (slowest members') fly speed! Such an army will rarely face difficult terrain or obstacles in the air, after all. But such an army of any significant size has a good chance of obliterating most campaign settings anyway, the airborne undead army's ability to run forever while flying being merely a footnote in the larger, sadder history of events. Faced with such an army, the end result's almost always the same: Just about everybody dies.