Encoding software for most lossy formats rely on some form of prediction and realtime analysis. That can't be the same for every repeated encode. Some randomness has to appear so that bit for bit, separate encodes are not alike.
$ ls -l KDE_Startup_new.wav
-rw-r--r-- 1 jerf jerf 970882 Feb 27 21:42 KDE_Startup_new.wav
$ lame KDE_Startup_new.wav 1.mp3
$ lame KDE_Startup_new.wav 2.mp3
$ md5sum *mp3
0bc5fee9b5d67ca2d6f1bf61a186067a 1.mp3
0bc5fee9b5d67ca2d6f1bf61a186067a 2.mp3Some multi-threaded encoders may be non-deterministic (from using concurrency), but encoding MP3s (or nearest equivalent) on modern hardware is generally fast enough for casual use even on a single thread, and parallelizing the operation would be better done at the level of tracks rather than within a track.
MP3 compression works by FFT-ing the audio stream, which is something that has to be ingested sequentially. It's not realtime since the encoder does it much faster than realtime, but it is doing sequential analysis of the file.
Usually a high quality encoder does multiple passes of the file to better fit it's FFT with the source material.