Most of the ones I'm thinking of seem to have a science fiction, mythic and/or fairytale feel to them, but I'm happy to see all sorts of interpretations, from the literal to something totally out there.

Covenant Call the Ships to Port. Swedish electronica. Lyrics

Adam Stemple Fool am I and Gene Wolfe Pastiche #12, and The Ocean Doesn't Listen. Folk rock with major blues and classic rock influence. I'll have to transcribe the lyrics, as I think my CD got lost in a move somewhere after I ripped it for my mp3 player. (edit: I've transcribed them here.)

Van Canto The Last Night of the Kings (lyrics) and My Voice (lyrics). German a cappella metal, usually fantasy/mythic/fairytale themes.

Blind Guardian The Bard's Song (lyrics) German power metal band, although this song more on the acoustic side.