Here's my latest thought. I can force a transaction fee for each output greater than 2. Normal users will only send transactions to 1 address with a address for the change. Only advanced users will use the sendmany api to send coins to many address at once. I can force a fee to use the sendmany feature. So for every output greater than 2, you have to pay an additional 0.1 LTC fee. Without the ability to send to multiple addresses at once, I don't think the spammer can bloat the chain cheaply anymore.
I think it's a great idea to pay fee if you are sending coins to more than one address at the same time - common user will never use that option and it will stop spamers!
You have my support on it.
