The problem is that there are no clear rules. Actually one cannot blame self-voting or mutual-voting accounts for doing that as the system encourages everybody to do it. Therefore solutions like the suggested diminishing returns which would just discourage certain voting patterns (instead to condemn them) look very interesting in my eyes.
Your second idea looks rather similar to the one @twinner suggested, and I think it is very interesting as well. :)
I do think some kind of self voting is essential, I would have never bought Steem Power if it wasn't for being able to upvote myself. Like you say, banning self voting won't work because of multiple accounts.
I'm looking forward to what the future will bring for steem in this regard.