Hello friends. Things are simpler actually. CE isn't fully deterministic just because it uses asynchronous multithreading approach (synchronous would perform very slow in this particular algorithm), so, if some thread is delayed by any reason (OS thread scheduling), the flows which movement it simulates are delayed as well, and won't have an effect on landscape, which would affect the flows, controlled by other threads. This is the cause of different results every run even when the same seed is used.
If to disable multithreading, CE always generates the same result with the same seed given that original terrain isn't changed.
BTW, thermal erosion behaves much better, although still may produce sudden changes if animated.
Daniil