Ok, your own server tells you that you are not allowed to relay.
That means: If you reply on Gmail to your own adress, something sent in that mail header is wrong.
(Or the error message veils something else.)
And yes, for a mail server you need an MX record, this is a name server entry that this host does actually act as mailserver. But the mail wouldn't even be rejected in the first place if there wasn't some entry somewhere, because the host wouldn't be found at all.
I'll try to explain what you actually need:
The mailserver has to have an MX record. The domain must also exist. Usally, you should get both from your ISP where the server is located.
Second, the mailserver has to listen to the mail port. Receiving mail and sending mail are two different things. Obviously, something does listen.
Third, when _sending_ outgoing mail, you'll have to set correct mail headers. With an easy setup, several smtp servers recognize the host and just add all necessary information by themselves. And I think here is you problem. Check the mail header of your own mail lying at Gmail's.
Right now, your server receives mail but seems to reject it.
What I would do: Log me in onto the server and make a telnet localhost 25 and construct a correct mail by hand and sent it to Gmail and reply to that. (If there isn't any obvious mistake in the mail header you've already got)
But I don't even touch sendmail, because I'm a total smtp idiot.
And imap has in a sense something to do with receiving mail, but usally your incoming mail would be took by your smtpd and transferred internally to your IMAP server where you can fetch it from anywhere else.
And it's totally possible that I'm talking utter nonsense because I'm not sure how your setup exactly look like.