...blocks are found at random intervals.

Every once in a while the network will get lucky and we'll find six blocks in ten minutes. If you are deciding what transaction fee to put on your transaction, and you're willing to wait until that six-blocks-in-ten-minutes once-a-week event, submit your transaction with a low fee.

All the higher-fee transactions waiting to be confirmed will get confirmed in the first five blocks and, if miners don't have any floor on the fee they'll accept (they will, but lets pretend they won't) then your very-low-fee transaction will get confirmed.

In the limit, that logic becomes "wait an infinite amount of time, pay zero fee."
...

Gavin Andresen

Yes, I see this as correct as well. If demand for space within a particular block is elevated (e.g., when the network has not found a block for 30 minutes), the minimum fee density for inclusion will be greater than the minimum fee density when demand for space is low (e.g., when the network has found several blocks in quick succession, as Gavin pointed out). Lower-fee paying transaction will just wait to be included at one of the network lulls where a bunch of blocks were found quickly in a row.

The feemarket.pdf paper ( https://dl.dropboxusercontent.com/u/43331625/feemarket.pdf ) shows that this will always be the case so long as the block space supply curve (i.e., the cost in BTC/byte to supply additional space within a block [rho]) is a monotonically-increasing function of the block size (refer to Fig. 6 and Table 1). The curve will satisfy this condition provided the propagation time for block solutions grows faster than log Q where Q is the size of the block. Assuming that block solutions are propagated across physical channels, and that the quantity of pure information communicated per solution is proportional to the amount of information contained within the block, then the communication time will always grow asymptotically like O(Q) as per the Shannon-Hartely theorem, and the fee market will be healthy.