I believe I found a solution now - and it's not a boost/thread-issue. The problem seems to be, that the console is mixing things up. If I write to a file instead of the console, output is in order. Still I don't know why, but I don't care either.