Suppose Alice and Bob wants to send messages through Sue without revealing to Eve that the exchange took place. Slightly more formally, I don't want Eve to have any advantage telling if Alice is sending spam to random recipients, or if Alice is engaged in an information exchange with Bob. Is this possible?
Eve tracks all communications to and from Sue, and might at any time get any internal information from Sue, except the private key of Sue.
There are other users sending messages through Sue, besides Alice and Bob, and Eve might at any time compromise any one of those users, but not all of them at once, to see what information that user is receiving, and from whom.
For clarity, an ideal solution would be if Alice and Bob use public key encryption, without adding any identifiers to the messages. Sue maintains only a single mailbox, so each user simply downloads all messages for all users. Bob knows which messages are intended for him, because those messages are the only ones he is able to decrypt. However, this would get impractical quickly as the number of users grow, but on the other hand would still require a fairly high number of users to be secure.
I have considered variations of onion/tor routing, but fail to see how this could be made secure given the requirement and the threat scenario: If completely random routing is used, the intended recipient will stick out in the noise of the total traffic generated each time Alice sends a message. If only a few infrequently rotated routing trees are used for each recipient, Eve might compromise the other users in those routing trees and track the layers of the message that eventually reaches Bob.