Feist? - definitely!
Beth Gibbons? - no doubt!!
Fiona Apple? - hell, yes!!
Also:
The Cardigans' Nina Persson is a cutie in
every respect...
... as is Judith Holofernes (Wir Sind Helden), who I'm glad to see mentioned here.
But what about:
Kelis (esp. I got a crush on her voice ever since "Kaleidoscope")
Kim Gordon (if there was any doubt why, her performance on "Sonic Nurse" alone should clear that)
and most of all
Roisin Murphy (has she really not been mentioned so far?! - well, her singing "Off on it" usually does all the trick for me

, seriously: she's my #1 sexy-female-voice).