This is what I mean when I say that an oracle would be needed to determine the formula relating difficulty to block size. There is absolutely no way to know what this formula would look like. The penalty for getting it wrong (and it would be wrong most of the time) is vanishing fees, resulting in hysteresis (wild oscillations in network hash rate). ASCIMiner's 24% of the network hash rate could become 51% after a difficulty adjustment.
The fundamental market logic behind that idea seems solid enough that it actually doesn't matter too much how the relation is calculated. There could be some limit for how much the block size can change which is what MoonShadow suggested, if it's feared that the change can be suddenly too drastic. Otherwise it's all irrelevant since the market will balance the block size regardless. If it's too high miners will stop due to lack of fees and incentive, leading to a smaller block size, if it's too low it will lead to more fees, more miner incentive, more miners, and a higher difficulty and higher block size.
What's wrong with the scheme I described, which responds directly to changes in transaction space scarcity?
What you described isn't a bad idea either. I don't have more advanced opinions on it yet, but it looked decent.