I've been handling offering flexibility in fixed big projects by sharing my Pivotal Tracker story board w/ feature estimates and letting them choose which features to axe to get their new priority scheduled.

In addition I've also been offering a fixed amount of "freebie points" for 'not yet discovered features'. That helps define that yeah, I'm going to do a couple extra things not defined in the scope, but it's fixed amount and when you've used them up, there's none left.