Well, she has two albums. The first one was released in 93/94 and is called The Divine Comedy, and is fantastic (in my most humble of opinions of course). Hard to describe, but there's a lot of different instruments used and a very 'earthy' and sort or renniasance vibe to it. MTV used to play her video for "The Gentleman Who Fell" all the time, primarily because she's, well, nude throughout it. You should be able to find the CD in most music stores or online at Amazon and the like.
Her second album is called The Peopletree Sessions and is more electronic based and somewhat experimental. It's good, but totally different from her first.
She was in a band for a year or two called "Plastic Has Memory" who never released anything but it's easy to find live recordings online. Kind of spacy etherial rock.
She has a new band now but they just started playing together so there isn't a name or recordings or anything like that yet.
Oh, she also has a new song on the Underworld soundtrack, but I haven't heard it yet.
Thanks! I'll definitly check out her albums. Like I said I love Millia eversince 5th element, and her "Big, big,Bada-boooom!!!"