Items "Of the Dark" are qlvl 6 and considered cursed. This means:
(1) A monster must be at least mlvl 6 to drop the affix.
(2) A dungeon source (chest, e.g.) can drop it beginning on dlvl 3.
(3) The affix cannot generate in town or from boss monster drops.
Mlvl 6 monsters are Horrors, Black Deaths, Shadow Beasts, Burning Dead Captains, and the like. These guys start showing up on dlvl 3, so that's not a bad place to start looking. You'll also have decent luck hunting through the early-mid Catacombs.
The only difference that game difficulty will make in hunting "Of the Dark" items is the base type of the items that you find. Higher difficulty monsters can drop more base types, so it's possible to get things like Full Plate of the Dark and so forth -- not that FPM of the Dark is useful to a BNM.
I would recommend playing at least Nightmare for cursed item hunts. Not only do you stand the chance of finding cursed items with interesting base types (consider a nice highly durable cursed Ring Mail), but you can also find some rare and interesting unique items (which many players like simply for the novelty value). Jewelry is another factor: low level monsters that could not drop jewelry in Normal will be able to drop jewelry in Nightmare. Monetary gains are better in Nightmare also, so you'll be able to pay for all the potions you drink while dungeon crawling. Logistically speaking, Nightmare's a good idea.
Regarding Helm of Sprits: Your analysis is correct in that it has a very small window of opportunity. HoS is qlvl 1; Overlord's is qlvl 7; Helm type is qlvl 8. By the time Helms can drop in Normal, any unique helm will be Overlord's. In Nightmare and Hell, the mlvl bonus to base type allows monsters mlvl 1-6 to drop HoS. It's still theoretically possible to find HoS from these monsters as late as dlvl 5, but the ideal hunting zone is dlvls 2-3 due to the low mlvl boss monsters.