From what I'm aware, the details of how you get to the fight in her lair are unimportant to obtaining the deal. You simply need to get her below 20% life and let her take a turn for her to surrender and offer you the hair.
My only guess for what is happening is that initial encounter of yours where you "Killed her" may have caused an issue with the game. As she only surrenders as part of her encounter in the lair, having her "Be killed" outside of that encounter may have removed the flag enabling her surrender.
