Now I get it. The "I play a little more fee than you" race allready started. Judging from the source[1][2] though the default setting is still to sort by priority first. Since priority is determined by age and size of the inputs the network currently gets either more expensive or slower. I havent actually noticed it while send btc, but the longer I look at the recent graphs the more I see that its now normal to wait a block or two even though you pay a fee. The strange thing is that the blocks are not full even though they could be, even with transactions paying fees. Is this miners afraid of an orphaned block due to slow propagation?

[1] https://github.com/bitcoin/bitcoin/blob/master/src/miner.cpp#L229
[2] https://github.com/bitcoin/bitcoin/blob/master/src/miner.cpp#L255