Perhaps in addition to the age priority rule recently implimented, there should be a minimum age rule without a transaction fee. Said another way, perhaps a generation rule that says that a free transaction must be 3 blocks deep before it can be transfered again for free. This will still allow real users to immediately spend new funds if they have to, while still permitting real users to reshuffle funds to suit their needs without an overhead cost. I think that this would significantly inhibit the type of spamming attack that is currently underway.
That could make people get tied up in their funds again. Think MtGox or even the bitcoin faucet. Faucet can only send out a nickel every 3 blocks, because each time it sends a nickel, it sends the change to a new address, tying up transaction fee free for 3 blocks.
Only a little. If the rule is generally known, and the reason for it, I think that those like the bitcoin faucet could adjust. I'm talking about limiting based upon the coins movement, if that's possible, not a three block ban upon a particular address. The new client has 100 addresses, correct? If bitcoin faucet has more than BTC .05 in each address, and simply rotates the addresses as the requests come it, then it can service 100 requests in half an hour without delay, and more with delays. I'm not saying that transactions can't be created, just that generators will not put them into blocks until the transaction that they depend upon is three blocks deep without a fee. With a fee, they can do whatever they want; and the generators probably wouldn't honor a 3 block delay upon a fee paying transaction anyway. This leaves the possibility of free transactions an open possibility, while inhibiting spamming. If there is a technical reason that this rule cannot work, I wouldn't know about that.
EDIT: Markets that are trying to service withdraw requests would know how many requests have been sent in the previous 30 minutes, and could choose to warn the requester that such requests may be delayed by this rule, or they can choose to pay a fee out of it.