I found it odd that I was also able to pick only “some” Very Hard chests, but at least 80% of the ones I’ve found, I couldn’t lock pick. So maybe you’re right about a “scale” of difficulty, and/or some Story chests may be harder than others (or easier?).
While I can’t answer your question fully, I know that at lvl 15 lockpicking, you should be able to unlock any Very Hard chest. Since I’ve reached level 15, there’s not been a Very Hard chest that I wasn’t allowed to open. With this theory, as long as you reach lvl 15 lockpicking, I’d wager that you can open story chests regardless.