Here are some ideas
Make voting patterns more visible. Right now in order to know someones voting habbits you need to go to Steemreports. If community benefiting voting patterns get rewarded and community destructing voting patters get punished with a public stamp it will become less of a problem. Good voters on top will get more votes themselves and bad voters get less votes.
Give higher curation rewards when upvoting smaller accounts. Minnows won't mind giving up 40% of a 5$ vote to the curator instead of 25%. This would also discourage big accounts just exchanging votes.
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.