My take is that the value of single dimension (i.e. linear result position alone) banded results for users and advertisers are severely limited and plateaued (or even decreased) as the number increased. In fact, for your case, inability to sort result is a huge drawback. Eventually your site are for advertisers as well as users.
The outcome of the UI should really depends what kind of business decisions are there. Nevertheless, as designers, you can influence the outcome of the design depending on how strict or flexible the business owner is.
For example for your case there are some unfurnished details which can aid you and business owner to formulate a more valuable banding.
1. is there limit on how many premium results are displayed at any one time (Google sets it at 3 on top)
2. Is the location of the results fixed or is there room for negotiation.
3. Is there some kind of others discriminants to decide which premium members of the same class belongs in the higher position
There are many more creative ways to deliver more valuable premium listings without sacrificing on usability. Some samples:
- Multiple premium location - top, left, in between normal result (not displayed in screenshot)
- Multiple level of premium - different shades and location
- Multiple type of items to be featured - seller and products
- Accessories - ribbon, color, pics, icons