Sorry to hear you're seeing those delays during the relay process! This is a known behavior and we have a development task opened to correct this since gateway communication should not require an MX lookup before being carried out.
Kyle Kerst
Lead Internal Network/System Administrator
SmarterTools Inc.
smartertools.com