You might try replacing/upgrading the factory battery cables too. My buddy's '96 Ford was always slow to turn over, and hence really tough to start if it wasn't plugged in to warm up. Turns out time had taken a toll on the cables, resulting in higher than normal resistance, and low voltage to the starter. After replacing the cables with some new ones that we made from 2ga copper welding cable, the truck whips right over and fires up without being plugged in. Granted that was at 5000', not 9000, but you still shouldn't be worried your truck won't start if it's above 10F or so. Something is just not right.
Emergency starting idea... My old deuce and a half had a flame heater, which basically lit a small fire in the intake pipe. It worked great to get the truck going in the cold without any pre-heating, as it didn't have a block heater or glow plugs. I've used a propane torch to the same effect a time or two in other tired diesels. Having the engine pull in warmed air seems to greatly aid starting, assuming it's rolling over fast enough...
Good luck!!