creating threatening villians

when players can interrupt an evil speech with instant magic, how do you keep villians intimidating? i find that my players dont feel threatened often against enemies. my current game is kind of a fairytale horror kind of deal (think dimension 20s neverafter series) and my party and i are mostly teen women, i am not opposed to killing off any PCs or NPCs.