Mobs that used to give Souls but do no longer:
Critters
The rep-less/loot-less mobs that attack the npcs at the entrance
Everything on the gunship
Blood beasts on Saurfang
Severed Essences (spawned from the Valkyr after Saurfang)
Zombies from Precious
The bugs in Putricide's "trap"
Marrowgar's Bone Spikes
Mobs that still do:
Deathwhisper adds
Rotface Oozes (only the big ones now though)
Putricide's Oozes
The Geists that spawn from the traps in the Plagueworks (do these traps still respawn?)
After completing the initial quests you will always debuff every mob you hit in the instance with Shadow's Fate - Spell - World of Warcraft which upon death will grant you one Soul. It's entirely possible for a warrior or ret paladin who's tanking a 10 man to just Demo Shout/Holy Wrath on the pull the debuff the whole pack and then swap to a sword and shield. Even abilities that do no damage will trigger the debuff so even Taunt, Chains of Ice, Desecration, Death Grip, etc will debuff the mobs.