The "stock" King Air 350 works on a 9 or less beacuse it only has 9 passenger seats (assuming no aft jumpseats). If your aircraft is Type Certified for more than 9 seats w/o a dual TC (such as the Sovereign) then it must be placed on a 10 or more certificate for any 135 operations. (meaning you can't just casually take the seats out of a G-IV and say look, 9 seats!)
If you have the jumpseats in a 350 and have a dual AFM supplement, passenger breifing cards, etc and all other interchangable data for the aircraft, then you can conduct 91 operations with 11 seats, and 135 operations with 9 with the HBC placard in place for the aft seats being unusuable. Same goes for the CE-680, it is a 12 seat aircraft, however the forward divan seat is removeable and doubles as a galley extension. There is a complete 2nd AFM supplement, weight and balance, and passenger briefing card arrangement which makes it legal to operate 9 or less 135 and a full 12 on 135.
Part 119 does not specifiy specifics regarding seating capacity, only through reference to 135.411(a) and .419 in the contents of OpSpecs. So, in truth, they both specificy a requirement, but the details are in 135.
But as I'm constantly reminded in life, I'm sure there is more to the story than I know.....