Out of the current revisions, lol sorry to say I really don't like anyone of them (I'm probably too picky, hehe). I think you were getting close to somewhere on the second one...perhaps some sort of stained glass effect might accentuate the lion.
I still think some experimentation should be done with other animals, simply for experimenting's sake. The lion is well suited and strong, and works quite visualls for this map. But try some other animals, and perhaps a few different versions of the lion (perhaps of just head and mane, to other things).