Our stories don't always fit in an iteration.
This means we don't actually finish a story every iteration. Sometimes a story is half done. Note that this does not mean that the software is broken or unusable; that's never an acceptable state at the end of iteration. What it does mean is that sometimes there's code in there that simply isn't usable by an end user - it's code that will be part of some feature X, but feature X isn't done and therefore isn't enabled. Think incomplete, not broken.
In practice, this works out all right from a code stability standpoint. Our automated tests make sure we haven't broken anything that we've said is done. However, from a process and a product planning standpoint it's actually a big problem.
Let's say I've signed up for a four-week (two iteration) story. Well, that means I should finish 50% of it during the first iteration. The problem is, until I've finished the whole thing, I don't really know what 50% is. Of the multi-iteration stories we've done since I've been at this job, all but one of them involved a last minute scramble because more than one iteration's worth of work was left in the last planned iteration. Reference the old cliche:
"The first 90% of the code accounts for the first 90% of development time. The remaining 10% of the code accounts for the other 90% of the development time."**
So, my rule for QA is very simple:
All stories must fit in one iteration.
If a story can't fit in an iteration, we trim it and split it and rework it so it does. Often this is hard to reconcile with the requirement that stories provide some use benefit, but we've always managed to make it happen.
* I'm not sure what's magic about two weeks. Iterations certainly could be just about any length, but two weeks is very popular.
** I don't know who said this, and Google turns up a lot of sources.