Our systems cannot send e-mail to a company that has no MX record. There is an SMTP server running on their IP address and they are able to get e-mail from gmail. Is it normal for mail systems to try to connect to a SMTP server at the A record when there is no MX?
Yes it is standard, per RFC 5321. Please see the Wikipedia page on MX Records
Normally yes, if no MX record exists, the A record should be used as a failsafe.