I like the hexproof idea. I think it could add a lot of complexity to the game without adding much complication. ATM magic runs amok, people keep stacking it because there's no downside. We've got quite a few units that have this 'supportish' ability, that are spammed remorselessly because the slows stack etc. I'd love to see a pack of buoys get minced when the slow they rely on can't keep a melee unit back.
You could even have specific immunities (like we already have, see pyro flame above), to tune factory matchups. If hawks were immune to slow that'd make them much better at killing rapiers, which they're supposed to be able to do anyway, but have you seen them 1v1? Having units that are immune to disarm could really breath some life into counterplay to thunderbirds and racketeer.
All this stuff necessarily slows the game down, and often they're part of strategies that can be obnoxious or even painful to play against. I don't think it's unreasonable to have units that sacrifice a little efficiency in order to become immune to specific battlefield dominating effects.