@Alex: I totally agree that there needs to be a feeling of progression. It's largely about, "how does this progression play out" and "have I locked out so many options that I feel paralyzed". The big problem with the current Skills is that if we've got all of them, we're gods. This is bad. However, what's also bad is not having the ability to diversify our fleet compositions because Skills make <that one path> so much better, long-term.
Using Story points to re-spec is a great idea, in that it removes some of the choice anxiety; if it's de-coupled to leveling, it's better, though; as it is, it's basically just another token you earn every time you level up, rather than something the player can grab if they're willing to go <do something>.
This ties in with the Hull Mods idea, among others. Instead of having the Freebie Hull Mods be something players save their Story Points up for, because they want a perfect endgame fleet... they should be encouraged to experiment with them, try out things.
Level caps and a limited burn-once resource like Story Points sound like they are, in general, make players want to min-max harder and make choice anxiety worse; ideally, a new player would explore all the Skill regions over the course of their first game, making different configurations as they understand what they want (as opposed to what the game wants). Story Points are, potentially, a great way to get there, if they're available and not tied explicitly to levels.