So looking at this service, and possibly other mixers, aren't they effectively just exchanging my transaction history with another stranger.
Correct. And that's why Chipmixer gives you a
signed receipt:
Every time you withdraw from ChipMixer, we give you cryptographically signed receipt that proves you have received those funds from us.
For example.
Alice deposits 10 mBTC into chipmixer and gets a 8 mBTC chip and a 2 mBTC chip. The chips Alice gets were from earlier in the week, so they don't have her TXN history.
Bob comes around later and deposits 10 mBTC and picks up a 8 mBTC chip and 2 mBTC chip. Bob does something bad with this chips and gets investigated. When they trace the coins Bob used, they ultimately trace them back to Alice, since Bob happened to pick up Alice's earlier deposit. So although this is great for Bob, Alice gets a knock on the door with questions about what she's been up to.
A mixer can't change any connection Alice had to a certain address before mixing the coins. If there are any ties between Alice and her 10 mBTC deposit, Alice can be found. This has nothing to do with Bob (who received the chips created out of Alice's deposit), the same thing could have happened to Alice without using a mixer.
But you said Bob "does something bad", that means Bob did this after receiving the mixed coins, and if that's what is being investigated, Bob can't pin it on Alice.