Any version of Exchange may fail some third-party relay tests, even when the server does not actually relay. To understand why, you need to understand the basics of SMTP and know how Exchange accepts or rejects SMTP mail.
Exchange doesn't check inbound SMTP mail against the directory during SMTP protocol conversion. Rather, Exchange checks only to see that the RCPT TO: matches the domains that you've configured the server to accept.
Exchange checks the mail against the directory only after the SMTP conversion is over, and it rejects the mail if the user specified in RCPT TO: does not exist. This behavior causes Exchange servers to fail some relay tests.
Exchange's SMTP behavior is both RFC-compliant and "by design." Microsoft chose to implement SMTP in this fashion, primarily for performance.
If you're running Exchange 2000 or later and you want to circumvent this behavior, you can do so by writing an event sink that performs a directory lookup during the SMTP conversion.
For most of us, though, it doesn't really matter when Exchange rejects mail bound for a nonexistent user, as long as it ultimately rejects the mail.