BM, I have been exploring a strategy using N-way mixing, where by 'mixing' I mean the proper sense of creating separate transactions to exchange the coins. Whitepaper/ppt/git forthcoming.

The gist of the idea is:

(1) N players use a randomized Byzantine process to agree on a mixing specification, and then
(2) Execute multiple pairwise transactions atomically on the Bitcoin blockchain, ala TierNolan's atomic cross-chain transfer solution. This is an N-way, same-chain atomic transfer within Bitcoin (ie not cross chain).

Atomic Cross Chain Transfer discussion
https://bitcointalk.org/index.php?topic=193281.0
https://github.com/TierNolan/bips/blob/bip4x/bip-atom.mediawiki

Example:
Alice wants to mix 1 BTC
Bob wants to mix 2 BTC
Charlie wants to mix 3 BTC

In step 1, they decide on the following mix:
Alice --> Charlie 1BTC
Bob --> Charlie 2 BTC
Charlie --> Alice 1 BTC
Charlie --> Bob 2 BTC

In step 2, Alice executes her transfer to Charlie, Bob does his to Charlie, and Charlie does his to Alice and Bob. This is done in a way such that either all transfers succeed or they all fail.

I'm currently working on final steps of extending TierNolan's solution and a prototype.

Yes, this means the players pay for more transactions. One of the advantages is that the temporal locality of the transactions is loosened.