Their most recent album is fantastic. Long songs, but damn good ones. Puppies keeps pushing the album Jotunheim is from but I've only listened to it once, so I can't really weigh in if I think the songs on it are too long quite yet.
So here's the deal with Verisakeet. I too had the same reaction when I first listened to this album (it was my introduction to Moonsorrow). The songs seemed way too long, the instrumentation seemed to all blend together, the vocals seemed unnecessary, the production sounded muddy, etc etc. I set the album aside for about 2 years. When I finally came back to it I had upgraded the headphones I typically would listen to music on. That made a world of difference. If you are listening to Moonsorrow on shitty headphones or speakers, you are missing out on a lot. The instrumentation is just so dense, with so much going on, it can't be replicated on cheap equipment. Now I realize not everyone can afford expensive high quality sound setups, but it really does make a difference. At the same time, I had become more accustomed to 15+ minute songs that are not Prog Metal epics. I had become more engrossed in Atmospheric Black Metal and grew a lot of appreciation for long songs that don't go into instrumental wankery to pad the length (see Dream Theater or most traditional prog metal bands). Also I dug into the lyrical content more. Being a band that only sings in Finnish, this was a little more difficult, but the lyrics are fantastic and the vocals fit the concept perfectly. I have come to love the album so much it moved its way up to my number 2 album of all time.
I know I pimp Verisakeet more so than their other albums, but that's only because I feel it is the best place to get a full appreciation of the band in their prime. However, their albums V: Hävitetty, Kivenkantaja, and Jumalten aika, as well as the EP Tulimyrsky, are all basically just as good. I mean Jumalten aika is basically just Verisakeet 2 as far as overall sound goes.