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
IT Coordinator
SmarterTools Inc.
www.smartertools.com