My colleague John Dolan wrote up a similar problem in one of his LC-GC "LC Troubleshooting" columns:
LC-GC 13(9) 708-712 (1995)
 I don't think LC-GC's on-line articles go back that far, so I'm sending you a copy via e-mail. 
In that case, the early peak was occasionally significantly bigger, but same pattern as your problem: the anomaly ocurred only sporadically, and re-injection from the same vial looked OK. The early peak in that case was around k' 0.3, so earlier than what you're seeing. The problem with early eluters is that the system is "out of equilibrium" right around t0, and random artifacts are common. If you look at the FDA's "Guidance for Reviewers" document, they suggest that k' should be > 2.
For what it's worth, the actual cause of the problem in that article was never identified (I subsequently spoke to the reader who had submitted the problem). The early peak was an internal standard, which was actually counterproductive, so they went back to good old external standardization.