We had the issue as well with our Cisco SPAM solution. Whitelisting the domain did work for us, though I do feel like sometimes I am not receiving a notification that I should.
Your Exchange admin is correct that directly connecting the two does pose security risks (how "real" or likely a risk...somewhat debatable, but still) and I know we certainly wouldn't allow it unless it was a last measure.