But how many of all transactions should on average fit into a block? 90%? 80%? 50%? Can anyone come up with some predictions and estimates how various auto-adjusting rules could potentially play out?
If you want the worst case then consider this:
Some set of miners decide, as Peter suggests, to increase the blocksize in order to reduce competition. Thinking longterm, they decide that a little money lost now is worth the rewards of controlling a large portion of the mining of the network.
1) The miners create thousands of addresses and send funds between them as spam (this is the initial cost)
a) optional - add enough transaction fee so that legitimate users get upset about tx fees increasing and call for blocksize increases
2) The number of transactions is now much higher than the blocksize allows, forcing the auto-adjust to increase blocksize
3) while competition still exists, goto step 1
4) Continue sending these spam transactions to maintain high blocksize. Added bonus, as the transaction fee you pay is to yourself - i.e. the transaction is free!
5) Profit!