Despite what one would think/hope, sending a message to a given address does not inherently give Google a high confidence that a reply from this address is expected (and, for example, that it should bypass spam checks). I have confirmed with Google's tech support that there is no way to automatically have this happen. The user can do the following:
1. Add the address to your contacts list in Gmail.
2. Check spam folder for replies, and mark it as "not spam" if something ends up there, which should influence the fate of future replies received. I can also approve an address at the domain level, i.e. if it is a big vendor or similar. I've had to do this with several of our Chinese vendors. I regularly ask engineering and purchasing to give me a list of the supplies we deal with, so I can approve them as a preventative measure.
For what it's worth, all of the false positive instances of reply -> spam we have experienced have involved the sender's email server having a problem. In the most recent case, it appears that the sender IP address appears on at least two internet blacklists. Since that is beyond my control, but we are trying to do business with these people, I can only add the domain to the approved senders list so that future replies from them should bypass the checks. However, if another company with a problematic email server replies to one of us, their message could very well still end up being marked spam.
Since Google can't help us, I am trying to figure out some kind of human process to defend against this, but to getting to a 0% false positive rate looks kind of ugly. One idea I had is to make a script that is invoked when a user sends a message, and somehow adds the recipient address to their contacts and/or some sort of approved sender list.
Has anyone done this?