I yanked a starter from a parts car today to test it, and it appears the issue was the rebuilt starter. Though I had bench tested it on multiple occasions with success, there must be an intermittent issue. The rebuilders assured me it was fine - they are not going to be happy to see me in their shop yet again...

Thanks for your suggestions.