The only solution is to use another channel to authenticate the other's key, be it GPG's web of trust, or any other imperfect way (phone call, physically meeting, ...)
First, Agree on a reply latency -- say, 1 day. Then, instead of simply replying to a message, you have an irritating four-step process:
1. Wait until one day after you received the message.
2. Send a digest of the message and your public key.
3. Wait another day.
4. Send the message itself.
The receiver must make sure that the delays for receiving the digest and the reply body are what the expect. This method requires a MITM to either anticipate what the message is or introduce an extra day of latency, which the receiving would notice.