You could cheat and use different keys for each recipient. That would work assuming the recipients don't know each other (and cannot compare keys).
Mix networks are by design hard to trace so it depends on the network.
EDIT:
Sending a message to Bob implies Alice knows how to find Bob in the first place, or knows someone who knows where Bob is, without Bob having to directly reveal his location to Alice. The Tor network has implemented this through hidden services which guarantees that both Alice and Bob remain anonymous to each other. The webpage has some diagrams as well and explains how it works, but I won't go into much detail about it because your question isn't about Tor.
It is important to note that public key cryptography doesn't guarantee anonymity or privacy or protection from identification. It's not designed for it. It just protects a message. Tor has managed to do a decent job at protecting two parties who wish to talk to each other and is reasonably mature but mutual anonymity really depends on the (onion) network Alice and Bob are using - not on the PK scheme.