This was quite a good question and despite some comments, is very relevant to security. It is also a real problem. Don't get caught up in the mirky details. instead focus on the general problem, which could be equally applied to real world issues faced by Journalists or pretty much anyone who lives in a country where government control and civil liberties may be at odds. Essentially, this is the metadata problem. A 3rd party does not need to actually know the content of communication to draw conclusions about what was in the communication. The fact these conclusions may be based on inaccurate or incorrect assumptions is largely irrelevant.
The general question is, how can party A communicate with party B without party C, who has access to party A's metadata, knowing that some communication has occurred?
With email, this is extremely difficult. There are other protocols which either have less useful metadata or which can allow the metadata to be obfuscated. However, the problem here is that party B may not be able or willing or even aware of these other protocols. The advantage of email is in its ubiquity.
If we assume the restrictions of the original problem hold i.e. party A cannot just get a different email address, then the most obvious solution would seem to be using the MiTM type scenario. Essentially, some form of relay where party A sends the message to party D, who sends it to party B and party B's respons is sent to party D and then back to A. However, this has a number of limitations as well. Party B (who is not cooperating) may observe that the messages are being relayed and become suspicious. Likewise, party C might wonder what the messages going to the relay point are and become just as suspicious, especially if C is able to associate messages going to the relay with some other behaviours and there is sufficient frequency. The problem with using any form of relay is that it doesn't change the overall metadata pattern - it simply puts another hop into the process.
Metadata is about patterns and pattern analysis. To hide communications at this level, you need to obscure the patterns. Instead of one relay, have multiple relays and use each relay for multiple recipients. Difuse patterns by communicating with many people (in the OPs example, don't just email your mistress, but many other women who are not your mistress).
I guess the point here is that everything you do leaves metadata. This metadata can be used to draw assumptions based on the patterns which are identified in the metadata. Anyone who argues that only people who have something to hide need to worry about metadata are failing to think about what kinds of assumptions creative people might be able to derive from these patterns. If those drawing the conclusions have sufficient power, the fact that the assumptions may be incorrect is irrelevant - if they believe the assumptions are correct, they will act accordingly and this may have adverse impact regardless of the truth. For those with sufficient power/influence, how your percieved can be as important as how you are - if your partner believes your cheating, your life will likely become miserable regardless of whether you are or not. If your government believes you are exhibiting patterns of data commonly associated with terrorist activity, they will likely treat you as such regardless of your actual actions and if your company believes they have identified you as the whistle blower based on metadata, you will likely find yourself unemployed regardless of the reality.
Metadata is valuable and potentially dangerous. It will exist regardless of what we want. It is important that access is controlled appropriately and access has adequate checks and balances. We cannot assume that because some metadata seems innocuous to us that it cannot be used by others, especially when combined with other sources. From a security perspective, we should apply the normal 'need to know' principal to all our data, not just the data we think is sensitive or important. We need to assume there is always someone smarter and more creative than us and if your going to cheat on your partner, make sure you have a separate net identity they know nothing about!