an easier method for less advanced users would be to simply let the original 'free' transaction go through, but for a seperate payment to the pool.
(i.e. you pay the pool 0.001 btc and tell them which free tx you want them to include in their next block)
that way novices don't have to figure out how to resend a transaction (which as far as I know, bitcoin-qt won't allow)
Taking the fees out of the tx itself would also allow for pool subscriptions. I pay 0.01 to "BTC Miner" and get a set amount of transactions. It would allow for economies of scale, i.e. bit-pay could get a better rate per tx than the guy that processes 1 per month. Dust transaction sites would have a different agreement.
edit: sites like btc guild could also "guarantee" transaction times (say 60 minutes or your tx fee back) based on their hashing power relative to the network.