There is a good reason why the Recipient Validation feature of ORF is disabled on Edge Transport Servers: Exchange does a better job there. Unlike ORF, it does not require direct access to your Active Directory, so if your Edge server gets compromised, your AD data is still safe.
However, once you install CU1 on your Exchange 2016 Edge Transport Server, things will turn sour quickly. A client of us, Microsoft MVP Norbert Fehlauer from Systema Gesellschaft für angewandte Datentechnik mbH have discovered a major issue with Exchange recipient validation that results in bouncing all inbound emails. The issue is now documented in the Exchange 2016 Release Notes.
No hotfix is available for the issue at the moment. We recommend temporarily disabling Recipient Validation (see Release Notes above on how) and keeping an eye on this — as a major argument for having an Edge Transport Server is doing recipient validation on the network perimeter, we can probably expect a quick update to be released in the coming days.
Update March 29, 2016: No word on the hotfix from Microsoft (rumor has it they plan to address the issue in a subsequent Cumulative Update only), but Exchange MVP Maksim Barakin investigated the issue and came up with another workaround that temporarily fixes the issue by disabling the recipient validation cache of Exchange using the following Exchange shell command:
Get-TransportService | Set-TransportService -RecipientValidationCacheEnabled $false
Caching is normally enabled on Edge servers and disabling it may have performance implications, so we recommend keeping an eye your server for a while after the change.
Update June 24, 2016: Although the issue is not discussed in the release notes of Exchange 2016 CU2, the newest CU seems finally to fix this problem.