How to fix these SOA DNS problems

As long as the system pointed at by the MX record has an A record itself, then yes.

For example: example.com can have a MX record pointing at mail.otherdomain.com. As long as the name mail.otherdomain.com itself is resolvable to an IP address, this is a valid configuration for example.com.

Strictly speaking, mail.otherdomain.com should be an A record with the IP address in order to be RFC-compliant. But this A record will be in the otherdomain.com domain, not in example.com.

Addressing your example, in order for bob@example.com to be a valid email address, mail.otherdomain.com needs to be configured to handle inbound mail for bob@example.com.

Your rDNS records will remain with your hosting provider. While they can delegate this, you won't be able to use standard techniques to setup the PTR records with GoDaddy.

I will use example.com for your domain as that is recommended domain for documentation.

Setup your MX for example.com to point to your mail server (mail.example.com). Setup the IP address for mail.example.com as an A record. You can create as many CNAME or A records as you want for this server, but mail is a good general purpose name that can be used in place of all the CNAMES you are using.

If you want to be able to browse example.com, you will need an A record for it. Configure www.example.com as an A record.

Consider setting up TXT records for SPF.

If you have a global IPv6 address block, you can configure IPv6 and add AAAA record in addition to your A records. Otherwise don't setup AAAA records.

GoDaddy will configure the SOA and NS records.

EDIT: Suggested temporary db contents. Use the correct nameservers from GoDaddy, these may be incorrect. Shut down bind after 2 days to a week.

When you move back to GoDaddy you will need to add address records for the domain, www, and mail as well as the MX record. This will have to be done through their web interface. I have added suggested SPF records. The records you need to add start with the first A record which is for your domain.

$TTL       1H
@      IN      SOA   ns1.godaddy.domain.com.  admin.mydomain.com.  {
               2011031200
               3H
               1H
               1W
               1H  }

       IN      NS   ns1.godaddy.domain.com
       IN      NS   ns2.godaddy.domain.com
       IN      A    111.111.11.111
       IN      MX   10   mail
       IN      TXT  "v=spf1 mx -all"

www    IN      A    111.111.11.111
       IN      TXT  "v=spf1 -all"
mail   IN      A    111.111.11.111
       IN      TXT  "v=spf1 A -all"

Once you have this setup try using the host command to check the values from godaddy. Start with host -a mydomain.com ns1.godaddy.domain.com. Also check the www and mail addresses. If they are resolving correctly and showing godaddys nameservers, then everything is setup. It will take a couple of days for any record pointing at your host to age out of DNS cache.