I think that the issue is really just one of terminology. I would argue that creativity is increased by an expanded card pool due to the additional possible permutations of card combinations. There's not really any way to argue against the math of the greater numbers.
It is one of terminology but not the way you think. Greater number of permutations is not the same thing as creativity. Any half decent composer can tell you that learning how to create and be creative within a restrictive form like blues form or waltz form forces you to find new ways of doing things, of challenging assumptions to get what you want out of it while having no restrictions can frequently lead people to just putting down notes on the page. Listen to some of the avant-garde or free jazz and you'll get what I'm talking about.
More options != Creativity.
I'm not saying they are mutually exclusive, just they are not equal. The question is one of degrees also. How many restrictions are there? In Star Wars your restrictions in the Core Set are huge. The resourcing mechanic as well as the pack style of deck building and the limited number of packs all create an enviornment that is almost hostile to building unique decks. This will change greatly in a couple years. I expect to see Star Wars deck building to show some very interesting elements. I also expect it to reveal that the game is much more about play ability than deck building ability (assuming the packs continue to show a reasonable balance).
Another nail in the coffin of this debate is the difference between restricted and banned. People seem to be focusing on the idea of "soft-banned" rather than at it as the use of this card gives me these options rather than removing the others. This is of course perfectly understandable, we've been taught to build from a very large pool of powerful and efficient cards. We are now being challenged to build with a pool every bit as large, but with more delineated choices.
To show what I mean about this, how many people complain about not being able to have three of a specific plot in their deck? What about two? One is the norm and that means when we get an opportunity to run two we view it as a positive. Every time we select a plot we chop down the number of other pltos that can go into our deck and there is rarely complaint about this.
That said. Why isn't KotHH on the restricted list? And I'm thinking all agendas on the restricted list might be a damn good idea.
I'm not sure this metaphor works, because it just leads to arbitrary analogies for what "restricted cards," "deckbuilding," and in-house" mean, for example. But let's talk through it a little. The game already has deckbuilding restrictions, just as music theory is applied so that we have common chord progressions, so for example you'll hear a I-V-I progression in a waltz, just as you'll hear it in blues. This is like saying that any deck can only have 3 copies of the same card. So it would make more sense to say that avant-garde would be me throwing my card collection on the floor of my apartment, shuffling them with my feet, grabbing a few handfuls and making a deck out of it. It certain would be "creative," but also most-likely nonsensical. A trained player can look at it and say, "Oh, I see what he's doing there. He put in FOUR copies as a commentary on the strictures of classical deckbuilding forms. Oh, look! He's added in an allusion to mill decks by including Corpse Lake, but comments on how it's meaningless because there aren't other discard effects in his deck." It might be nice for novelty, but it isn't tournament-legal, and certainly not competitive. It will never make it "to the top of the charts" so to speak.
Let's tease out another example: Let's take your analogy of the restricted list as being like composing music in certain forms. Waltz is to Viennese Waltz as Greyjoy choke is to Greyjoy Winter choke. I can compose Viennese waltz in 3/4 and 6/8 time, but because of its tempo, it's sometimes much more efficient to do so in 6/8. It's as if you're saying that because we can no longer compose waltzes in 6/8 time, we should be thankful we can compose more regular waltzes, when there's some poor composer out there whose ability to compose sea chanties was greatly diminished. But let's ground this analogy a little: The Winter agenda allowed houses weak in card advantage to shore up that hole. That combined with the watershed of winter effects in GJ and Stark is why it was popular in those houses, and why they became T1. However, card advantage is also a problem in Targ, so restricting the agenda across the board also had relatively more impact on the possibility for a Targ player to use the winter agenda as a means to shore up that weakness.
But this whole anaolgy is tired. Bottom line is that this does indeed limit creativity because any player remotely concerned about efficiency must pass up less likely, more creative options for answers to his deck's problems, simply because they happen to be mainstays in power-decks.
Your point arguing the difference between banned and soft-banned is essentially one of semantics and not practicality. Competitive players will almost always choose the most efficient card. While a card does have more or less relative efficiency based on which deck you put it in, some cards are just flat-out better, and so by choosing the best choice to the exclusion of the others, you have a smaller card pool. It is not "every bit as large" by definition. It seems more likely that the enemy to creativity is efficiency itself - which goes back to play-style - and has little bearing to the size of the card pool. Limiting options is limiting options. And the design team by expanding the restricted list is merely readjusting relative efficiency, which in the short term feels like creativity, but it's not.
Lastly, people don't complain about not being able to use 3 plots because it's been a part of the rules for forever (it's part of the accepted forms, if you will). There probably were such complaints back in the early CCG days when you could use 2 plots in the plot deck, and then it transitioned to only 1.