Setting MX records with Registrar vs. Nameserver Host

1) Absolutely. When a DNS lookup is done (in this case, to see where to send mail), that lookup is done from the nameservers. So if your nameservers don't have the MX record listed, the lookup will result in nothing.

It's the same as a phone book--except imagine that you can only list your phone number in one phone book at a time. So you tell your friends "Look me up in the Acme phone book." So when they want to contact you, they look your phone number up in the Acme phone book, find your listing, and call you. But then if you move your listing to the "OtherGuys Phone Book", but don't tell OtherGuys what your phone number is, when your friends look you up in OtherGuys, they won't see your phone number--because it's listed in the Acme book instead.

2) This is because the nameserver records for your client domains were cached for a while (typically for several hours, possibly up to several days--the timeout is configurable). This means (roughly) that anyone who did an MX lookup prior to you switching nameservers, kept the old information in memory for a while, so they wouldn't have to look it up again. But eventually, that information expired, so when they tried to look the information up again--this time from the new server--they got "nothing", so the mail started bouncing.

1. Yes
2. DNS caching. Once the timeout has expired things started going to hell.

Each domain has what is called an SOA record. It defines, among other things, how long other servers should cache information about where to request records for said domain.

As an example:

@   IN  SOA     nameserver.place.dom.  postmaster.place.dom. (
                       1            ; serial number
                       3600         ; refresh   [1h]
                       600          ; retry     [10m]
                       86400        ; expire    [1d]
                       3600 )       ; min TTL   [1h]

Once a query is made for something at place.dom (MX, TXT, etc), the location of where to make all future requests is cached for a maximum of 1 day. In your case it was much longer so you didn't notice because the SOA was cached.

To get more information about the SOA record for a domain try this from the command line:

~$ nslookup
> set type=soa
> set debug
> zaplabs.com
Server:     192.168.1.1
Address:    192.168.1.1#53

------------
    QUESTIONS:
    zaplabs.com, type = SOA, class = IN
    ANSWERS:
    ->  zaplabs.com
    origin = dns1.name-services.com
    mail addr = info.name-services.com
    serial = 2002050701
    refresh = 10001
    retry = 1801
    expire = 604801
    minimum = 181
    AUTHORITY RECORDS:
    ADDITIONAL RECORDS:
------------
Non-authoritative answer:
zaplabs.com
        origin = dns1.name-services.com
        mail addr = info.name-services.com
    serial = 2002050701
    refresh = 10001
    retry = 1801
    expire = 604801
    minimum = 181

Authoritative answers can be found from:
>