Transactions either require a fee (because they are small or the coins aren't aged long enough) or they don't require a fee.
Any analysis of fees should take into consideration (and discount) satoshidice transactions, as they are generally a house-of-cards, where one transaction relies on previously relayed coins that have no confirmations, these will languish until the original transactions are confirmed regardless of fee included. For example there is
a transaction that has paid double the required fee but has not been included because it is funded by several other transactions which are also not confirmed.
The inclusion of "free" transactions in blocks is up to miners (pools). Here is some of the parameters a pool can alter without needing to alter the Bitcoin client:
-blockminsize=<n> Set minimum block size in bytes (default: 0)
-blockprioritysize=<n> Set maximum size of high-priority/low-fee transactions in bytes (default: 27000)
We should first look at how Bitcoin handles transactions that require a fee but don't include it (which can only be sent with an altered Bitcoin). The parameter "minimum block size" is a default value of zero, meaning
no transactions not including the minimum per-kb fee will be included. If this is raised to a much higher value by a pool, this means that even spammy free transactions can be included anytime the block is smaller than this minimum after including all normal transactions. No pool I know of alters this (without some further code changes) because it just provides a free way to spam the blockchain with no benefit to anyone but the sender. Only pools like Eligius allow for some free small transactions, using their own rules, transactions that other Bitcoin peers generally won't even relay.
Then lets examine how transactions that qualify to be free are handled: there is a "free transaction" window of 27KB (of a maximum block size of 500K). This is what makes high-priority transactions free. However, they must still compete for just a small part of a block with other high-priority transactions, ranked in order of priority, but this space reserved for high-priority transactions is rarely full, meaning that high-priority non-fee transactions are almost always included in the next block. The Bitcoin client doesn't even prompt for a fee when sending a high-priority transaction.
Finally there are normal transactions, these are ones that pay at least the minimum fee as required. As of 0.7.0 (when run by a pool), they are sorted by fee, so that ones that pay more than the required fee are ranked more highly than minimum-fee-payers. This "paid" area also can include high-priority transactions that have volunteered a fee.
In conclusion, one must properly analyze all available information about a transaction (priority, size, time relayed, funding source) before evaluating the effectiveness of paying more fees. However, one can simply examine the default rules of Bitcoin to determine if volunteering more fee is of benefit.
