Can you up the fee to an existing transaction that you already sent? Assuming you are using bitcoin-qt?
I'm not aware of any easy way to do this at the moment. Hopefully, in the future there will be multiple methods of handling such a situation.
Technically there are a few things that could be done:
Someone could contract with a few of the major pools and offer compensation as an incentive to confirm specific transactions. They could then collect payments from individuals along with the transactionID that needs to be confirmed. They could forward the transactionID to all the contracted major pools. Then when a pool confirms the transaction in their next block, the service could release payment directly to the pool (keeping a small fee for themselves for providing the service).
The recipient could create a new transaction that spends the output they are receiving to another address they own even though it has no confirmations yet. They could include a large enough fee on this second transaction to cover the necessary costs of both transactions. Pools could start looking ahead to see if they can increase their profits by confirming an entire chain of unconfirmed transactions instead of just looking at each transaction individually. Seeing that there is an additional transaction with a significant fee that they could earn, they would have an incentive to confirm the earlier low fee transaction in their next block before some other pool gets the opportunity to collect that fee from the later transaction.
Does this mean that there is a payout of fee's after each confirmation? I was of the understanding that all fees was given to whomever solved the next block. The same principle as new coins.
Your understanding is correct. When a transaction is first confirmed in a block that is accepted by the network, the fees go to that miner (or pool). Additional blocks that are added to the blockchain are considered additional "confirmations", but those blocks only pay the fees from their own transactions to the miner (or pool) that creates them.
How does this prevent either of the scenarios I've presented?
Scenario 1. I'm a merchant. I receive a lot of transactions without fees. I contact a few of the major pools and offer a contract whereby I present them with a list of transactionIDs every 5 minutes, and they guarantee me that they will include all the transactions with those IDs in the next block they solve. As compensation for agreeing to this service, I offer to pay a daily sum equivalent to 0.006 BTC per transaction from my list included in a block to the contracted pools that create he blocks with my list of transactions.
Scenario 2. I'm a merchant. I receive a transaction for 10 BTC, but no fee. I immediately spend that unconfirmed 10 BTC transaction in a new transaction that sends 9.998 BTC to my bitcoin storage address and pays 0.002 BTC in fees. A miner (or pool) can now choose. In their next block, they can confirm two unconfirmed transactions that someone else has made that each pay 0.0005 BTC in fees (0.001 BTC for the pair), or in that block they can confirm my 2 unconfirmed transactions receiving 0 in fees for the first one, but 0.002 BTC for the second (which works out to an average of 0.001 BTC each). They get a 100% bonus for choosing to confirm my transactions. My transaction with the fee cannot be confirmed until/unless the free transaction behind it is confirmed first, so there is no risk that someone will confirm the fee paying transaction and leave the free one unconfirmed. Every miner (or pool) has a financial incentive to include my two transactions. If they don't do it right away in the block they are currently working on, then someone else might get it in the next block, and they'll be left with the cheaper transactions that only pay 0.0005 BTC in fees.