Craigsnedeker, I think you hit the nail on the head and answered your own question!
I watched both videos on youtube. I'm betting the Kutlass video was storyboarded thoroughly--it'd be too much to try to make that story out of random shots. I'd also bet the Letter Black video was just shot with the band acting out a "live" scene several times, then cutting the footage together and putting in extra footage for effect here and there. (It'd still be a good idea to have a script of some sort here before you just start shooting footage, though.)
In my opinion there aren't any 'rules' where you have to do it one way to do it "right". Guns N Roses did both styles and they made good videos, really (Sweet Child O' Mine and Don't Cry are examples, one from each "mold" you see here.)
I'm pumped about reading that Videomaker article now. I've been toying with ideas for a while and I'm anxious to see what others think about this. Good topic!