Release 8.1: Who/when to sign off stories?

I have a problem:

I am still ensure as to what criteria should be used - formally - to sign off a story at the end of an iteration.

I am a velocity preacher, and I also devote a lot of attention to the fact that the velocity figure we produce at the end of each iteration is meaningfull and can be reflected upon and discussed during our retrospective meetings.

Velocity is innacurate if:
- we have not estimated consistently tasks of similar complexity
- we measure delivered stories using inconsistent criteria for each.

I also find it really hard to actually define what "consistent story acceptance" should look like. So far, I have managed to still produce a Velocity that has "meaning" by making sure that the team agrees what the sign off point of stories should be, but I am not convinced I should feel particularly happy not to have an answer on this.

Also, on some projects, the number of people (who are genuine customers) who need to sign stories off as delivered is such that it is virtually impossible to sign off stories within 1 iteration. As I also preach the Story Velocity over the task velocity measurment, I cannot be happy with this.

I am still banging my head on that one, if anybody has any ideas or experience to share.....