[I'm with an SEM that manages ~100 advertisers who spend $250K+/mo each on search]
I think % of spend is the best model, not because it's an ideal model but because it's better than other models.
Problem with performance-based models: there being no S&P 500 Index against which to measure your SEM firm's performance, the only real way to know how they're doing is to either manage a similar campaign yourself and compare them to that, or have another firm manage 50% and compare against those results. But either of those approaches defeats the purpose of outsourcing.
Likewise, the bucket-of-hours approach lets the SEM nickle & dime you to death. There are certainly tons of things to do on a daily/weekly/monthly/quarterly basis for a large campaign, and I oftentimes think our clients have gotten used to the 'open bar' that a % of spend model allows for.
My own opinion is
a) take the % of spend model and cherish it, for it allows you to get a lot more value from the SEM without incremental fees
b) take the time to verify that the SEM is actually capable of handling all the work you want them to do. Lots of firms claim to be full-service, but in most cases that's them telling you what they think you want to hear. Likewise, know what SEM scope you will want to continue to handle yourself; knowing what part of the SEM workstream *you're* ready to sign up for and deliver on will help you decide which firm is best for you.