AbdulAlhazred
Legend
With the Bounded Accuracy rules I have in the 4.5 Edition the "To-Hit" issue you have when facing tougher challenges in 4th Edition somewhat disappears. The cumulative bonuses and penalties do not become as important to hit. Damage and Hit Points becomes more important and allow you to use a wider level range of monsters. However, if you still find it an issues, you could consider adopting the advantage concept from 5th Edition which is more straight forward I would say.
Yeah, in my game I didn't set out to use 'bounded accuracy' per-se. I don't really subscribe to Mearles logic on that to be honest. Still, I did end up with a more compressed overall bonus range. In 20 levels you get about 17 point increase in attack bonus, so maybe half what 4e gives you overall (there are only 20 levels in HoML). The idea was less about broadening the range of monster effectiveness across levels and more about just de-emphasizing the constant bonus seeking. The most benefit you can get from permanent bonuses is generally +3 (they don't stack, if you had a +3 weapon then you've pretty much maxed your permanent bonus, though +3 weapons are pretty much mythic items). Likewise +5 is the maximum attribute bonus (and attribute increases are modest, you could start with a +4 and likely increase that by one over the course of the game). I did find that I had to have a bit stronger level bonus than in 4e to keep damage and hit point increases in check though. The upshot is you don't NEED to run after pluses. Even if you had NOTHING but what you started with at level 1 you'd only be behind the most maxed-out PC by 4 points of attack bonus at 20th level. Significant, but small enough that you could compensate with other build elements.
The upshot is, the range of levels you can use a monster at is numerically about the same as 4e, but that represents a 50% greater swath of the total play range. By level 5 you are about 3 points ahead of level 1, and the level 5 damage expression is about 2x the level 1 damage expression. Level 5 monsters have about 2x the hit points of level 1 monsters as well, and of course their defenses will increase by about 3 points. PCs actually don't quite keep up in base damage increases and hit points, though they aren't far behind. The difference is made up more by increases in their other capabilities. Power effects tend to be a little more weighty in HoML, but simpler to handle and a little less frequent (you can trade 'surges' for more power uses though, which is an interesting dynamic).
I think you end up feeling a bit more outmatched in raw fighting damage-generation than in 4e, where PCs tend to be quite far ahead on that score. It FEELS more dangerous, and it can BE more dangerous if you get into a bad spot, but you always have the option to dig into your daily resources and fix it. At least if you don't keep getting into those spots! I feel like this rewards thoughtful play a bit more. 4e is tactical, but it tends to reward just wading in and relying on clever combos and such to be your edge. That might not be enough in a HoML game...