Nick Cave's version is unlike most other sung versions, because Stack O' Lee existed quite separately in the song tradition and the "toast" (spoken verse) tradition. Cave's is essentially a "toast" version set to music. The "toast" versions are generally ruder, and involve Stack O'Lee in sexual escapades as well as horrific violence.

An interesting version in this regard is R.L. Burnside's, which Samuel L. Jackson covered in the movie "Black Snake Moan"; it's also one of the "toast" versions, and is basically spoken word accompanied by blues guitar (or a full band in Jackson's cover). Jackson's is on the BSM soundtrack, and Burnside's on his album "well, well, well." You can also hear a pure "toast" version (no musical accompaniment) on the compilation CD "Get Your Ass in the Water and Swim Like Me," from Rounder. You can buy all these CDs or mp3 downloads from Amazon.

One of my favorite versions is Bromberg's. The title is funny, because it's neither a lament nor from Mrs. Delion's point of view--but it's a great song!