Two-headed mutant is really annoying.
I'm pretty sure it's set to only ever spawn once per run.
So for instance if you quickly run through a map or retreat or whatever, some kind of flag gets set in your savegame or character, and the two-headed mutant will never spawn again.
Depending on how you moved through the game this means you could make the mutant spawn without realizing it, and then erasing him forever by leaving the map.
To increase your odds of finding him try revisiting Depot A at various times, but if he already spawned once and you had to retreat or didn't notice, he probably won't ever spawn again, I wasn't able to ever respawn him on the same character even with reloading to a point before entering Depot A.