My code is heavily multi-threaded. This problem doesn't show up in single threaded environment at all. My OS is SUSE 11 and g++-4.3.3 as the compiler. I may have to post some code eventually but on the top off your head - do you have any pointers for me?

Note that free functions like asio::async_read/aync_read_untill (async_write/async_write_until, etc) are composed operations so "... The program must ensure that the stream performs no other read operations (such as async_read, async_read_until, the stream's async_read_some function, or any other composed operations that perform reads) until this operation completes" (http://www.boost.org/doc/libs/1_53_0/doc/html/boost_asio/reference/async_re ad_until.html). Also note that most of Asio classes (sockets, timers, etc.) are not thread safe. So in multi-threaded program you have to use some kind of synchronization if there is no implicit strand (http://www.boost.org/doc/libs/1_53_0/doc/html/boost_asio/overview/core/stra nds.html). The simplest kind of synchronization is asio::io_service::strand. If you use something else (for example, mutex) then notice intermediate handlers created by composed operations (http://www.boost.org/doc/libs/1_53_0/doc/html/boost_asio/overview/core/stra nds.html, asio_handler_invoke) and use your synchronization in a right way (for mutex see https://github.com/boostcon/2011_presentations/raw/master/mon/thinking_async hronously.pdf, struct mutex_wrapper at page 95-97). There is a feature named "Handler Tracking" (http://www.boost.org/doc/libs/1_53_0/doc/html/boost_asio/overview/core/hand ler_tracking.html) that can help you to investigated the order of handler invocation. Regards, Marat Abrarov.