Another idea I had, was to put it back to paying out tiny coins again, but also accepting transactions using those coins at no fee. The two problems with this plan would be: 1) the clients will still think they need to pay a fee unless you hack them, and 2) it leaves less space in our blocks for normal with-fee transactions. Currently undecided. It also wouldn't be very easy to write.
How about
Keep a queue of pool miners that need to be paid (say, balance >0.01 at the end of this block) ordered by how much they're owed.
First add miners who are owed more than 2 BTC to the block you're working on. Then add transactions ordered by profit. Then add miners owed less than 2 BTC until there is no room left. Alternatively, treat the payments as transactions having a transaction fee equal to 1/100th of what they are owed and just rank them with the normal transactions. I guess you'll need to to do a little fancy footwork for computing the size of the generated transaction.
In this way people will get paid out as fast as possible when the volume of paying transactions is low, and slower when it is high. This would reduce the number of paying transactions the pool must forgo in order to pay mining wages, though I suppose there aren't any currently
. You could make this more attractive by changing the payouts to include the fees, since then any slowness in the payout would be directly related to increased income for the miners and just increase your average pool payment per second a bit to compensate.