This is the key, I think. With Master of Magic out, Nightmist is ready to rock and is quite powerful, but perhaps the most interesting thing about Nightmist is when Master of Magic is NOT out, giving the player the interesting choice of whether to focus on getting Master of Magic or focusing on contributing directly to the battle.
Yeah, when I played the game originally I was like "I love how simple this system is, but I fear there is not much they can do with it".
Nightmist challenges that a little by being very flexible yet straightforward, and I agree that she is more fun before you get Master, but if you want to actually WIN it is a good idea to get it out early... there is no prize for fighting with one hand behind your back.
Btw... I love flipping her deck and trash so almost everything is in the trash and then using that to heal her... I forget the card names for that combo but it is great.
Mists of Time + Mistbound Recovery 
I like to call that combo "Mistbound Recovery..... OF TIME!"
If I haven't got Master of Magic in my hand from the start, it usually pops up within a few turns of using Investigate, at which point I can start using it to heal myself of the damage I did myself trying to find it ;).