I think we should limit restraints on deck-building as much as possible. Between starting element and highly specific skill trees, needing to devote deck-building to your element on top of that is too limiting, and won't allow players to go with their particular play style.
The way I see WoE is this.
Your skill tree is the equivalent of skills in other games. They are what defines your character/class. Everyone should be able to have a unique skill build. I agree with the way they are built right now. It gives you a lot of freedom in choosing your skill build, which is important.
You Home Element represents your devotions, who you work for. If your home element is say Fire, then you play in order to make fire the best element. But the important thing is, Just because you work for Fire does not necessarily make you a Fire Elemental. This means that although you work for Fire and it is much easier to obtain Fire cards compared to other cards, you do not necessarily have to build a deck that is based on fire, and you don't necessarily have to field a Fire Mark.
Your mark represents the type of elemental you actually are. I agree with making other marks somewhat difficult to obtain, so long as other things are not so restricted. It should be difficult to learn to metamorphose, as you are essentially changing your basic make-up, even if you do not change loyalties.
With that said, your deck is like your equipment. They represent the current tools you have to defeat others with. You should be able to use any deck, with no restrictions, as even though you work for your home element, you are not limited to waging war with their weapons. However, you DO know the ways of you home element better, so you should gain a small bonus when using 50% or more of cards from your element. For example, an EXP bonus when winning, or a small salvage bonus.
This is what makes the most sense to me thematically.