Custom search results for custom taxonomies

Okay, I'm building a business directory using Custompress: http://directory.probizservices.com/

So far, so good.

Step 1: What I would like to do is create two types of listings: Preferred Partners and Regular. I would like to have the Preferred Partners listings show up first in search and category results.

Step 2: Eventually I would like to restrict the publishing of Preferred listings to paying members, through some kind of membership plugin.

I am interested in the best way to do this. Is this something I could figure out or will it require lots of custom coding?

I think I can handle the part about two types of listings. Not sure about customizing search results. And I'm curious about what sort of plugin could restrict access to the preferred listings on the back end.