Well, after coming back from a long break, I have some good progress to report.
I tried implementing a grammatical system for algorithmic composition over the break and had a good deal of success in my endeavors. Although I created only a rudimentary composition language and a very basic phrase generator, the results seem more natural and interesting than any other method explored thus far, which means progress!
After a great deal of thinking on the subject, I've decided that a grammatical system might be the key I've been looking for to a successful path to my goals. The trick is that I can use a grammatical system as the underlying paradigm for other methods. In other words, I could have an evolutionary model that uses an underlying higher-level grammar to generate phrases. In theory, this idea is really no different than using an evolutionary model to generate an equally-abstract number that corresponds to a certain pitch (a MIDI note event). I could do the same thing with Markov chains and state-transition matrices.
There are a lot of places to go with grammatical algorithmic composition. I have a feeling I'm just scraping the surface of something big. Let's hope I'm not let down.