When I was tracking down my issue, the starter was an early fix. My first OEM reman was DOA, too. Even stranded me at the office. I had the dealer swap it out and the next one was good. It didn't resolve my issue, but it just shows that even OEM can be bad out of the box....
FWIW, my issue presented randomly, mostly when the engine was hot. Turning the key caused nothing. No ticking, never even tried to start. My CEL was always on. I tried swapping the relay, replaced the battery and the battery cables and the no starts continued. I found a thread that pointed to possible fuel issues and so I swapped the prefilter sock. My truck has not had a single fail-to-start issue since. That was about 8 months ago (and went through a NC summer).
So while I recognize that fuel issues shouldn't present itself there, the systematic change of parts showed otherwise (in my case).
This may not be the same issue you are having, but like you said, it's a solid PM move for these old beasts.
-D