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
System/Network Administrator
SmarterTools Inc.
(877) 357-6278
www.smartertools.com