If someone can flood the network with free transactions to/from their own addresses, and there's no way to make sure legitimate transactions are unaffected, there'd soon be no such thing as a free transaction any more. Would it be so bad to disallow them to conserve resources? The difficulty I imagine, would be in enforcing a minimum fee that would be remain sensible as BTC's value varies.
...was proposed years ago to solve the spam dilemma...proof-of-work. If you want to issue a free transaction, the network could require a small proof of work for such transactions.
As for requiring 'proof of work'; requiring a BTC value inherently does that (they could join a mining pool to do the 'proof of work', then use their earnings to pay the fees).