Switching hosting, keeping mx records

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.

The normal way of doing it is to leave the DNS name servers alone and to add/update the records in the zone that are pertinent to your hosting of the customer web site (A or CNAME records). There's no good reason as far as I'm concerned to move the name servers just because you're hosting the web site, unless you have some contractual agreement to do so or if the web hosting provider has a requirement to do so. As an example:

company.com:

Name Servers (NS) = Network Solutions Email (MX) = Google Web Site (A, CNAME) = 1AND1.com