The basic idea, as I understand it, is that if these parts were omitted, it's a case of meshaneh mimatbeya shetav'u chachamim - altering the fundamental text that the Sages instituted for the prayers. This itself invalidates the prayer.
So for example, the correct text of Shemoneh Esreh on Rosh Chodesh is supposed to include Yaaleh Veyavo. If one leaves that out, then, effectively the person has not said Shemoneh Esreh properly - it would be as though they omitted one or more of the regular blessings.
There are some cases where it's questionable where one should repeat the prayer because of such an omission (because there is the counterbalancing concern of a berachah levatalah, a blessing in vain, as you noted). In some such cases, the posekim recommend repeating Shemoneh Esreh as a voluntary (nedavah) prayer, which one is anyway permitted to do (see, for example, Taz to Orach Chaim 118:2 and 582:1).