Recipient Address verification (also known as “Callout” or Call forward ), which is what you described as “check the eligibility of the recipient” can be cascaded over several MTAs if they support it, should not take longer than fractions of a second, if the MTAs in the chain trust each other. Or you have some internal greylisting 😉
If you have a proper mail gateway, it is also possible to check for eligible mail addresses via Active Directory or LDAP. Then you would not need the callback verification.