If you manage to complete a favor for someone at the Riften or Solitude stables, its possible to be able to take the horses for free. While it isn't uncommon to be able to take "low value" items from NPCs when you become friends with them (or someone in one of their factions), a horse seems way too valuable to be able to just take for free after completing a small favor.
I was able to figure out a way to solve this issue.
For the two horses (000984A1, 000984AB) at the Riften Stables - change the ownership from RiftenStablesFaction to Hofgrir
For the two horses (0009B7A2, 000CE66F) at the Solitude Stables - change the ownership from SolitudeStablesFaction to Geimund
Not sure exactly why the NPC ownership works while the "Faction" ownership setting doesn't, but from my testing even if you were to befriend either of those two guys (or their replacements) at the two locations the horses still can't be taken without paying the 1000 gold coins.