I.M.E (I run a campaign featuring a lot of arcane spellcasting villains, both wizards, sorcerers and warlocks) having their abilities at will is worth more than you give it credit for. It's not so much about running out, as about having everything you can do at your fingertips at all times. I agree wholeheartedly that they're not as destructive as a wizard or sorcerer, but on the other hand they're less fragile. And they're not supposed to replace casters anyway, they're more a sort of inverted bard. (Versatile, but focused on messing with enemies rather than buffing allies.)
As for challenge, I'll say it again: CR is descriptive. If a 5th level warlock can't give a 5th level party a reasonable fight (and I agree, most likely he can't) then he's not CR 5. That's what CR *means*.
If you don't cotton to that, however, there are a few tricks you can pull to up damage output:
- Quicken Spell-like ability (available at CL 10, so probably level 9, 12 at the latest) a must-have feat for warlocks who want to deal damage
- Mortalbane (from BoVD), available at level 1, requires evil, but we're talking about villains here, anyway (and ones with easily fiendish fluff, at that)
- Empower Spell-like ability (available at level 6) not that impressive on its own, but great synergy with Mortalbane.
And while these are limited in uses per day, by your own admission, that's not so important for an NPC, right?
As for challenge, I'll say it again: CR is descriptive. If a 5th level warlock can't give a 5th level party a reasonable fight (and I agree, most likely he can't) then he's not CR 5. That's what CR *means*.
If you don't cotton to that, however, there are a few tricks you can pull to up damage output:
- Quicken Spell-like ability (available at CL 10, so probably level 9, 12 at the latest) a must-have feat for warlocks who want to deal damage
- Mortalbane (from BoVD), available at level 1, requires evil, but we're talking about villains here, anyway (and ones with easily fiendish fluff, at that)
- Empower Spell-like ability (available at level 6) not that impressive on its own, but great synergy with Mortalbane.
And while these are limited in uses per day, by your own admission, that's not so important for an NPC, right?