The only time the "Not Enough MP" message is displayed is when a target is Charmed and simply doesn't have enough MP to cast the spell that was randomly selected.

Unless I remember incorrectly (a distinct possibility), in FFIV (the SFC version at the very least), MP needed to cast a spell is subtracted at the moment casting is begun (as opposed to upon casting). Spells in a menu may be dimmed out based on MP at the time the menu is generated to prohibit the selection of a spell which cannot be cast due to a lack thereof. Due to this, schematically it would appear to be impossible for the player to initiate casting of a spell which could fail based on lack of MP.
However, if a character’s MP is siphoned away after the menu is called and before it is dismissed, it is not updated and the player can select a spell which should be greyed-out (this was not the case in FFVI, and probably also V). In the case of this anomaly, the game will see the PC go through the required casting time before calling the dialogue box in question: “Not enough MP.”
That's usually the other possibility, but the number of monsters that cast Psych/Osmose are far and few between (there's the Dark Sage, and the Insectus monsters in FF4A, the Insectus uses it as a magic counter though).
Obviously, the message is also seen whenever a monster attempts to cast a spell as a matter of course without enough MP.
No, that
never happens. Monsters
never consume MP. Consider Scarmaglione (the "living" version). His primary attack is Thunder. If Tellah syphons all of his MP, his attack will still occur, regardless. If Thunder ever misses, that's due to magic evade that all characters have except for Dark Knight Cecil.
It might sounds strange, but Toad is probably the most useful spell of the bunch, given the implications of the status itself vs MP consumption.
Are there enemies which Tornado would fail on, considering the period in which the command is available …?
Other than the bosses, no monster is ever immune to the spell. It may be difficult, but that's
only because there is a level comparison done.
The Tornado spell has the boss bit set, so it always fails to work on a boss. On the other hand, the one on Abel's Lance is not, which is the only difference. I'm not sure if any other property is different, other than the "set monster to death" vs when Abel Lance's Tornado is used. I believe a custom version of the spell is written for that weapon anyways, the original spell would not do that, even if the boss bit was removed.