While assassins may be somewhat expensive and their success is not guaranteed, the abrupt elimination of enemy commanders can be highly disruptive to enemy forces. Because assassins strike before armies move, sending in a few assassins can kill all the leaders of an army, pinning it in place and denying it magical support. Even one or two assassins can sometimes result in only half of an army participating in an intended attack, leading to defeat in detail.
If your mages have the right magic, you can also use remote assassination spells like Seeking Arrow or Mind Hunt. This allows multiple magi to target any province on the map with multiple assassination attempts in a single turn.
Spies and some magic items can be used to foment unrest in enemy provinces, reducing your opponent's gold income. If unrest reaches 100 or higher, unit production in the province is halted. Doing this to an enemy castle can seriously interfere with his war plans.
Army annihilation spells
Armies can be felled en masse. Sometimes this is done with battlefield magic that affect all foes present; there is also ritual magic that can target enemy armies in arbitrary provinces.
Murdering Winter, Fires From Afar, Flames From the Sky, and to a lesser extent Leprosy are ritual spells that can disable whole armies. Make sure to follow up the spell with an attack by a conventional army, since the units not killed by the spell will be at reduced hit points; they'll be harder to finish off next turn after they've had a chance to heal.
Good battlefield spells include Rigor Mortis, Rain of Stones, Astral Tempest, Fire Storm, Earthquake and Poison Vapours.
Not all battles are for conquering and holding territory; it can be worth it, especially for highly mobile or stealthy forces, to target individual provinces for some particular value and do damage before the province is retaken. Damage can take the form of, e.g. capturing a province, cranking the tax rate up to 200, optionally hanging around for a turn to pillage or blood-hunt (thus pushing up the unrest even more), and then leaving it with 1 PD, fully expecting the enemy to take it back. (And if not, oh well. You keep getting taxes.) This works particularly against enemy fortresses if you don't have time to take the walls down and thus can't build PD or expect to keep the province long-term.
Routed troops will flee into neighboring friendly provinces. Make sure that no such provinces exist for your enemy! Use the "magic" movement phase (together with stealth armies) which comes before the "normal" movement phase to conquer all the enemy provinces around the main "battlefield" province. If the enemy army in this main "battlefield" province is routed and has no province to flee into, all enemy units are lost and your foes will hopefully think twice before attacking you again. Check the army size graphic after such an battle. Take a screenshot from it and send it to your human opponents as a warning.
[It actually doesn't seem to be necessary to use the "magic" phase. If an invading army A is cutting into B's lands, and A moves from newly-conquered land L to attack B's land M while B simultaneously attacks L with airborne forces or reinforcements from elsewhere--if B captures L successfully then when A loses at M, A has nowhere to retreat to and so routed units die. The lesson here is that having well-defended forward bases helps invading armies recover from unpleasant surprises, even if you don't need the provinces for income. In particular, it keeps mages alive, since commanders almost always survive a rout.]
Some rituals like Fairy Trod allow you to move an army in the magic phase into any enemy province. Other spells like Cloud Trapeze allow an single Commander to teleport himself into an enemy province. Other (cheaper) spells like Imprint Souls or Call of the Wild or Ghost Riders summon a small army into any enemy province. Such magic 'Paratroopers' armies attack together with stealth armies already hiding in the target province and having the order "attack province". Force your enemy to patrol his lands and invest his gold into province defense. Keep in mind that battles initated by magic come before normal troop movement.
Super Combatants & Thugs
Particularly formidable commanders, such as Niefel Jarls and a number of pretender types, can become extremely dangerous on the battlefield with appropriate magical gear, orders and perhaps a few spells. Some such commanders can conquer enemy provinces alone and are called Thug or Super Combatants (SC).