Devi usare le sincronizzazioni. Anche se le funzioni di windows sono thread-safe, lo sono solo per la linea che in quel momento va scritta, non per un gruppo di linee.
Tieni anche presente che se vuoi che i thread scrivano secondo un certo ordine preciso, non basta mettere un mutex, in quanto la schedulazione dei thread è casuale.

Io userei gli eventi ( CreateEvent () etc. )