Out of interest, can pools take requests and manually include TXs, as you describe?
If so, maybe an automatic service could be set up whereby we can add TX fees at a later time, by getting all the major pools to subscribe to a list of fee free Txs that have had a bounty paid by the user to get included in the blockchain. Which ever pool does first, gets the bounty.