Should Majora come back? Hell yes.
Majora's Mask was a brilliant game in terms of storyline and mystery. That made it great, of course, but I would really like to have some mystery revealed. And Majora is one of those great mysteries. The evilest, most destructive and most insane enemy of the entire Zelda series could really do with a little backstory, IMO. They don't need to "explain" it having the personality it does. I'd prefer they didn't, actually (Majora should be just as insane and evil as before.) But I would like to know a little history on what the hell Majora is. Such as: is it a demon like some of us think?
I can't really agree with Zemen that Majora would have to be restricted to Termina. Several people were capable of transporting between dimensions, such as Link and the Happy Mask Salesman, so I don't see why Majora wouldn't be able to, considering how powerful and enigmatic he was.
That doesn't mean I don't want Majora to appear in another Termina based game. In fact, I liked Termina a lot, and would really like to see it in another Zelda game, Majora or no Majora.