Tycker det första låter grammatiskt korrekt, men jag kan inte svara på varför. Kanske har att göra med att om egentligen betecknar meddelandet och att det då blir en upprepning? Följer tråden med intresse, någon kanske har en bra förklaring :)
Jo du har helt rätt TS.
"om" borde vara med.
Jag skulle ha skrivit så här: "De som berörs av detta kommer att få ett meddelande om att beställningen inte har gått igenom"
(Det går helt ok att skriva "deras" två gånger, men man brukar sträva efter att få ett bättre flyt i text, så därför skulle jag skrivit som ovan).
Du som ovan kommenterar med att båda sätten nog går - du gissade bara va?
Visst förstår man ändå men det är sådant här som utarmar språket: små felaktigheter, okunskap om korrekt formulering, och vips, så har man skrivit skojiga meningar som blir tvetydiga, otydliga och i värsta fall kan missförstås.
http://www.vanligaord.se/om.php
hittade en länk på hur man använder ordet ?om? håller med någon om att använda ordet ?om? låter som talspråk.
I ts exempel så fyller inte ?om? någon funktion, (se länken) varken en preposition, adverb eller subjunktion. 
Kan tänka mig att det skulle vara ok att ordet ?om? används när en beskrivning av meddelande ges (vad det handlar om) skulle klassas som preposition antar jag
Det är faktiskt en intressant fråga!
Det funkar ju bra på engelska: "They got a message that their order had not gone through."
Det finns andra svenska konstruktioner med ordet "budskap" som funkar utan om. Man kan nå ut med budskapet att ...
Jag tänker att om man ser meddelande som ett objekt, som ett mejl eller ett brev eller en cykel som i exemplet ovan, så krävs det ett "om". Om man å andra sidan syftar till meddelande som det innehållet, eller budskapet, det har, så funkar konstruktionen utan "om".
Ordet "om" används tillsammans med "tala" och uttrycker att någon berättar någonting.
Ordet "om" betonas.
För dig som vill veta mer om hur ordets används.
"Om" kallas verbpartikel i satsläran och används för att bilda predikat tillsammans med "tala".
Nils "talade om" vad han hade gjort på semestern.