Khwarezmid Empire executed a convoy of Mongol merchants, and later envoys largely unprovoked. Mstlslav of Kiev executed Mongol envoys, even though all the envoys wanted to say is that the target was the Cumans and not Kiev. The Japanese eventually executed Mongol envoys as well. Currently listening to a history of the Mongols, and provoking the Mongols seems like a spectacularly stupid action, but opposing nations kept executing Mongol envoys. Why?
To answer the question of "why does everyone murder Mongol envoys", no not every polity the Mongols encountered executed the Mongol envoys. For example, the Yuan dynasty dispatched multiple rounds of envoys to Japan to order the Shogunate's vassalization before the first invasion. The envoys survived. Also, the Yuan dynasty sent envoys to the Tran dynasty of Vietnam prior to the second invasion and they safely returned. The history of the Mongols highlights the execution of Mongol envoys to illustrate the act as a casus belli for the Mongol invasions of the Khwarezmids, Kievan Rus and Japan. A major reason for explaining how the Mongols expanded was Genghis Khan feeling a certain polity disgraced him personally by executing his envoys. It is also more of an illustration of an (albeit frequent) exception to the norm, since diplomats entered polities under safe-conduct.
As to the essence of your question on why these polities executed the Mongol envoys, it has to deal with the particular historical circumstances of the polity doing the murdering. For the Khwarezmid Empire, they were quite paranoid, as they felt the Mongols were seeking to ally with the Abbasids against them. Thus, they felt the envoys were Mongol spies and executed them. For the Japanese, prior to the second invasion, the Mongols had sent the envoys with explicit instructions that the Mongols wanted the Japanese to respond, since their earlier envoys had been sent back without any response. With this quandary, the Shogunate had the envoys executed. For the Kievan Rus, the Cuman khan, after the Mongols successfully conquered the Cumans, fled to the Kievan Rus, as Mstlslav the Bold was his son-in-law. Mstlslav of Kiev allied with Mstlslav the Bold and the Cumans against the Mongols, so it was around these historical circumstances he executed the envoys. Hence, context is key to answering this question.
Sources:
The Secret History of the Mongols
Michael Prawdin, The Mongol Empire: Its rise and legacy
I've read before that the Mongols, Genghis Khan in particular, were early proponents of the idea of diplomatic immunity and that they would retaliate with extreme force in response to the violation of it. Is this true?