This is exactly where I am with Magma. I started with them a few months ago after hearing guys like Kavus Torabi speak so highly of them. Needless to say it's been going very well. I do think that Kobaia and 1001 Degrees are incredible. To me their sound lies between prog and jazz-rock. It's hard to explain but what really hits me (compared with most things labeled jazz-rock) is how many great melodies there are. With Kobaia I feel like they pretty much perfected their sound right away, so their only option was to change up their sound. With 1001 you notice that they're doing more vocal-oriented stuff. Maybe even better than Kobaia. Actually this early period reminds me of Godbluff-era VDGG. Just in the way the songs are constructed, how they ratchet up the intensity over and over again. Also I do think the Soft Machine comparison is valid, though their methods are very different. I also have the Univeria Zekt album which is very good if you like those first two albums. It's a bit more playful and has some English vocals (gasp!) but there's one piece that Vander composed called "Africa Anteria" (it takes up about a third of the album) which is maybe the catchiest thing he ever wrote. I can have that one on repeat for a while.
As for MDK, I had my first listen to it last week, and it totally blew my mind, particularly the second half. I was not expecting it to get that intense, in spite of what I've heard about the album. I really wish the quality of the recording was better (Vander's drums seem to get drowned out!) but the music itself is really something else. I'll have to dive back into that one soon. As far as "first listens" go I find it hard to remember another one that hit me so hard (maybe A Little Man and a House and the Whole World Window). So yes. They definitely live up to the hype.