It seems like part of the problem with blocks not including transactions is the maximum block size of 500kB. Doesn't this pose a scalability problem?
...
The size of the queue of unconfirmed transactions waiting for inclusion is known by your client but can't be viewed. It can be seen here:
http://bitcoincharts.com/bitcoin/txlist/. At this immediate moment, there are 2763 unconfirmed transactions (1454847 bytes). That would seem to me to be larger than the maximum blocksize indicated above, so the above rule about higher transaction fees may be kicking in on the miner's side for inclusion of transactions (but the client isn't prompting).