When you start the monitor it resets your Arduino.
If your Arduino was in the middle of sending data when it was reset, the last bits of data might make it through to the monitor.
As the monitor could have started in the middle of a byte transfer, the bits are in the wrong position and the monitor sees bytes which represent the characters you are seeing.
You should implement some error control, like packets with a known preamble, so your python app can discard data until it sees a known pattern.
This might do the job!
For now it stop giving me random characters. However, the problem does not always occur. I will give it some time to see whether this is the right hack.
Why don't you precede each valid message to the monitor with a known preamble, even one character like '*' that otherwise does not occur in your data stream. Then only grab data from the monitor starting past the preamble symbol.