OP claimed in this question that:
Every mantra begins with the word ॐ (Aum/Om).
Is that true? Are there any mantras that don't have ॐ in them?
Almost every mantra begins with OM. The reason is given below.
The syllable Om is the root from which the Vedas have sprung. (Every rite, therefore, should commence with the utterance of that syllable of vast import). Of him who has uttered for him the syllables Om, Namas, Swaha, Svadha, and Vashat, and who has according to the extent of his ability, performed sacrifices, and other rites, there is no fear in respect of next life in all the three worlds.
Mahabharata Santi Parva Section CCLXVIII
One notable exception is the Rama Taraka Mantra which does not begin with OM.
Some of the information contained in this post requires additional references. Please edit to add citations to reliable sources that support the assertions made here. Unsourced material may be disputed or deleted.
Every mantra should begin with the pranava OM otherwise it is considered as lifeless as per the following verse:
मंत्राणां पल्लवो वासो । मंत्राणां प्रणव: शिर: । शिर: पल्लव संयुक्तो । कामधुक् भवेत् ।।
The mantra is the body.And Pranava OM is the head.When the body(mantra) and the head(OM) are connected only then the recital(of the mantra) bears fruits.
Also, see this post to know why not only mantras but all Vedic recitals should begin with the pranava OM.
However,as per the Mahanirvana Tantram,which is a Shakta Agama,mantras in Kali Yuga are more effective if preceded by HREEM (the maya beeja) instead of OM.
In the Satya, Treta, and Dvapara Ages, the Mantras, O Kalika! were in their application preceded by the Pranava (9); but in the Kali Age, O Supreme Devi! the decree of Shankara is that man do perform all rites with the aid of the same Mantras, but preceded by the Maya Bija (10). All Mantras in the Nigamas, Agamas, Tantras, Samhitas and Vedas, have been spoken by Me. Their employment, however, varies according to the Ages (11). For the benefit of men of the Kali Age, men bereft of energy and dependent for existence on the food they eat, the Kula doctrine, O Auspicious One! is given (12).
Mahanirvana Tantram Chapter 9
NOTE-Hreem is called the maya beeja which is present in many famous Devi mantras.Other some important beejas are Kleem(Kama Beejam) Aim (Vaga Beejam)
It is not mandatory,
Some of the famous tantric mantras like
Navaarna mantra (navakshari chandi mantra)
Bhuvaneshwari mantra (hrillekha)
Ganesha Mantras (six lettered (mantra mahodadadhi 2.2),
Dakshina Kali mantra (Mantra.Mahodashi 3.2)
Ucchistha Ganapati mantra (mantra mahodadadhi 2.32)
Do not begin with Om and there is no need to prefix Om. There is one more belief that in the tantric literature, "Hreeem" is referred to as Shakti pranava which is as good as Om or Aum.
There are many more mantras, which don't start with Om (or Aum). For example: Da Bei Zhou Mantra, Ra Ma Da Sa Sa Say So Hung Mantra, Ajai Alai Mantra, Soham Mantra or Hanuman Mantra.