At O+8, a fully enchanted Dark Horse has +25 expertise without any runes. His orange blocks up to level 139.5 plus this number, which is 164.5. Medusa's base (enchanted) expertise is also +25. So to beat Horse, she needs a minimum of +14.5 Expertise from runes, and that only works if Horse has no expertise runes.
This, along with the huge amounts of Tenacity handed out at O+7 and O+8, makes Medusa's stone ability far less useful than it used to be. However, Medusa is still one of the most powerful heroes, especially in Expedition and War, She's the only real counter to Bone Dragon's energy drain ability, and she makes damage heroes much more powerful, since they don't waste their excess energy when they pass 1000.
If you want to see the true power of Medusa, pair her with Bard (which you're already doing), Wee Witch, Cyclops, Void and other heroes with really good whites, and never run her on auto.