How about this idea! The algorithm is updated to deny any blocks that have transactions in them that are less than 1/10th of the average (or median) transaction fee from say the last 300 blocks. That does mean that the currency isn't effectively divisible... but it isn't anyway! In that your transactions will never get processed if you send them with less than the lowest fees (as the fees start to rise). It would then become quite costly (in bitcoins) to launch such an attack.

If you like this idea, send some bitcoin happiness to
1Gc3BAjW4jD1GCCphdqCSNsWHFHGyu8k4f

I just joined the craze last week! :-)

Daniel G
Apologies if this idea has already been mentioned...