Yes, it should be part of the protocol itself. DASH does this right now. In the wallet you can choose to send funds "anonymously" or "non-anonymously" with a single click. The mixing is facilitated by the full nodes, so there is no need for a 3rd party mixing service.
Dash uses masternodes if i am correct, which means the user has to "trust" masternodes not to censor them. Kind of a logical failure i think
The mixing is better if implemented at protocol level, for ex - Cryptonote protocol