Melheds execution was a clear step towards deeper hatred and increased warfare. Fingolfin couldnt possibly know that you had alreayd given the order, and as such his letter stands (and even if he knew about the execution order, it would obviously still stand... you killed my knight!).
Fingolfins next step is to punish Jaeger. With Melhed (as far as we know at least) using scrolls in northern Thalmarkin, you have brought scrolls upon yourself. Fingolfin did however forbid people to use summoning scrolls, and he bloody cant let people do as they please after he has told them not to :p Even though it might be ok now by default, Fingolfin still hasnt given the ok to the people with scrolls, and they are thusly breaking his command. Unthinkable! Now we have to see what is punished most hard, lies or breaking command...
Melhed certainly isnt put in an easy position, but lets get yourself out of it!
As for Maya, if Melhed is the realm they make themselves to be, she should have no problem with getting reelected if she should loose the crown.