This page at bitcoincharts shows a list of transactions that didn't get included in a block yet. Many of them are from 2 or 3 months ago, even though they include a fee. What's going on? Why haven't they been included in a block already?
1 Answer
From what I have read about Bitcoin transaction confirmation (aka mining), a transaction may not be included in a block for any reason, but the most common is that the fee is too low for the size of the transaction. A higher fee increases the chance that the transaction will be included in a block by a miner. A transaction with no fee may eventually be confirmed, but it could take a long time to do so.
Certain transactions cannot be included in a block because they violate the Bitcoin protocol and will be discarded. Among others, these are transactions that attempt to spend more Bitcoin than is in an account and tranactions that try to double spend an accound balance. Transactions that depend on other transactions that have not been confirmed yet and are retained until either it is dropped because it would violate the Bitcoin protocol, or it is added to a confirmed transaction block.
(source: https://www.rugatu.com/questions/42/why-do-some-transactions-take-months-to-get-into-a-block)