You are right that it is a bit of a dilemma... There is a separate table that tracks order totals, and the module simply inserts the priority handling charge there. Since the mechanism defines it separated from the order header, a search does not bring it up. This is not unusual... try searching for "ground" (or some other shipping method) or try searching for something from a line-item, such as a product title--same result.
Make a long story short, it would be somewhat of a hairball to display the priority status on the order summary page for the admin view because the architecture has it separated. If you feel adventurous, you can play with ./admin/orders.php, but don't expect a quick one-liner solution.
If you're comfortable with doing MySQL queries, you can try this:
SELECT orders_id FROM orders_total WHERE class = 'ot_handling'
Otherwise, I'd suggest using a separate status as a work-around. Make a status that easily identifies the order as a "priority" order to you. When a new order is received, you should review it in detail as part of your normal process anyway--at this time, you will see the priority handling charge as one of the totals. Set the status to "priority processing" for those order that paid for it, otherwise set it to just "processing." Now, you can see at a glance which orders are pending and which have priority.
Cheers,
markus