Beyond multiclassing, many melee fighters will tend to make use of "cheese" to beat fights. Examples include Polearm Mastery/Sentinel, Booming Blade/Dissonant Whispers, or ridiculous AC boosting.
In your estimation, is the CR system reliable at that level (or at least as reliable as it is at any level)? In other words, can I build XP budgets into encounters for 8 PCs and have them be reasonably challenging and balanced?
Another thing is that even at 6th-7th, PCs are notoriously hard to kill. I am guessing by 11th it is all but impossible aside from save-or-die effects. if that is the case, how do you build tension into combat encounters?
.
The fact that they can take on such deadly encounters so easily is due to 2 main factors. Those monsters were almost all affected by Protection from Evil/Circle of Evil, and Hold Person + Paladin Smite is incredibly effective (used in dragon encounter, used to kill a beholder without it getting a single action earlier). So, CR/XP encounter building can be very very swingy depending on what is being fought, what spell capabilities the PCs have, and what tactics they can employ. Protection from Evil can change the dynamic of play, for example, so it's a good idea to keep enemy types in mind when building encounters, and watch out for spells like Hold Person.
5-7 sounds like a better idea, closer to the traditional sweet spot at which D&D has been most functional. I can say from personal experience running 5e that it's definitely not at it's best at 1st level, and swiftly improves. By 5th there's none of the problems you saw at 1st. On the upper edge, I'd only be speaking theoretically. The past editions 5e most strongly resembles philosophically and mechanically - AD&D and 3.x - never worked well at high level, so there's little reason to expect 5e to. At 11th, though, the fighter does get his extra attack and the barbarian his relentless rage, so they're kinda peaking in a sense.Every year I build a sandbox for play at conventions and for next year I am considering going a little higher level (11th) than what I have in the past (5th-7th).
How are you using Hold Person here? On what enemies? I'm curious.