Sometimes this is really simple: button X used to say cancel and now it should say Cancel. Check the install case, the upgrade case, the doc, any marketing or training materials, and you're pretty much set.
Sometimes this is more complex but achievable: a new login mechanism. There are numerous test cases to try here, but in general it's a straightforward problem.
Then there are the really hard ones. How do you accept a story (feature, backlog item, etc) that simply says, "spend 1 month hardening the HA mechanism in the product"? It's really tempting to say something like, "all existing tests must pass, and the bug count for this particular product area must be <>
I think this is wrong, though. In a sufficiently fast-moving product there may not be a time when all tests pass on all branches, or that window may be really tiny and very late in the product cycle. Do you really want to wait that long to decide whether you really think you've accomplished your goal?
I think instead that stories (features, backlog items, etc) should be treated as unacceptable (ha!). These aren't things that are going to be tested directly, and therefore they shouldn't be accepted directly. After all, what you're really hoping to accomplish is more of a general statement about that area of the product - "It's more stable" - than a specific goal - "It's 2x faster". So treat it as a general acceptance, and fold it into the general testing that you're doing, both during and after development. Also, make sure that any substories that are specific can be drawn out and tested separately. Whatever's left - this general statement - is the thing you have to treat generally and test generally.
There's danger in attempting to make the general too specific; the things you've left out of the generality are the things you're not testing - and that's risky.
I'm not completely sold on this yet, but it's the best thing I've come up with.