Hide the fact of e-mail communication

Bob has a mistress. Her name is Alice. Bob`s wife Eve knows Bob is unfaithful, but she does not know who the mistress is. Alice does not know Bob is married.

Bob needs to communicate with Alice over e-mail, but he needs to use his personal address (bob@bob.bob) and the e-mails must be sent to personal address of Alice (alice@alice.alice), otherwise Alice would be suspicious why she could not use her personal address.

Eve decides to monitor Bob`s e-mail communication and e-mail communication of all his possible girlfriends to find out, who the mistress is.

Is there any way for Bob to hide the fact he communicates with Alice? PGP encryption is not a solution: it hides only content of message, not a sender nor a receipient.

I thought there could be some trusted "friend-in-the-middle" Fred who communicates with both Bob and Alice. Bob could send e-mails to Fred with a real receipient in the first line of PGP encrypted message. Fred would decrypt the message, read the receipient, encrypt it again and send to Alice, so Eve would think Bob communicates with Fred and Fred communicates with Alice and there is no communication between Bob and Alice.

Is there any typical solution of this problem?

EDIT: Alice can cooperate in the way she encrypts her messages (because Bob's mistress would surely be security-conscious), but she needs to use her personal address and she needs to recieve e-mails from Bob`s address.

EDIT II: (for my girlfriend) I am not Bob, I have no mistress and my girlfriend is no monitoring my e-mail communication, well, I hope :-). I am looking for a technical solution how to hide communication between two given e-mail addresses. That is why a divorce is not a solution and changing one of these addresses is also not a solution, because it changes the original meaning of my question :-)...