I've setup a catch-all to forward all emails to my gmail account, and this works. I can receive email from any @mydomain.com, and send email through my server. However, if I jump into gmail and send an email from that to @mydomain.com it doesn't work. I don't get no error back saying it failed to send, it just never appears in my gmail (I've checked spam.)

Any idea what's going on?

I have a similar issue, never bothered to figure out what it was but for me the mail only appears when I click "All mail" in gmail. It seems to skip the Inbox and doesn't go to spam either. Maybe you have the same?

Just clicked 'all mail' and what-cha know, email appears. Weird. Do you think this is a gmail bug or maybe something our end?

I follow this guide: http://blog.tech4him.com/linode-setup-d ... orwarding/. Did you do the same thing?

If you send a message from Gmail to another server, which then delivers it back to Gmail, it will not show up in your inbox. If you search you should find some threads talking about this.