What is the exact formula for calculating transaction fees?
See GetMinFee() in main.h for the code which determines the minimum transaction fee.

The part you're describing is implemented as follows:

// Raise the price as the block approaches full
if (nBlockSize != 1 &amp;&amp; nNewBlockSize &gt;= MAX_BLOCK_SIZE_GEN/2)
{
    if (nNewBlockSize &gt;= MAX_BLOCK_SIZE_GEN)
        return MAX_MONEY;
    nMinFee *= MAX_BLOCK_SIZE_GEN / (MAX_BLOCK_SIZE_GEN - nNewBlockSize);
}


where:


nBlockSize depends on who we are:

if we're a user making a new transaction, nBlockSize is 1
if we're a node deciding whether to relay an incoming transaction, nBlockSize is 1000
if we're a miner deciding which transactions to include in a new block, nBlockSize is the size of the block we're building before adding the new transaction

nNewBlockSize is the size of the block including the new transaction
MAX_BLOCK_SIZE_GEN is 500kB
MAX_MONEY is 21 million BTC (all the money in the world)


so it's saying:


if we're either deciding whether to relay or mine the transaction, and adding the transaction would make the block over 50% full:

never allow a transaction that makes the block 100% full
otherwise scale the fee up by a factor of 500kB / (500kB - nNewBlockSize)



Note: by rearranging the symbols, we get exactly what Meni wrote in his answer:

Fee = Normal fee / ((500kB - size) / 500kB)
         = Normal fee / (1 - size / 500kB)