Wildcard DNS and CNAME

Unfortunately, what you're running into is a limitation of the DNS specification. Having an MX record for the same hostname as is defined as a CNAME record will fail in most DNS server implementations. Some older DNS servers will allow this, but they have been mostly phased out in favor of newer, more secure implementations.

Instead of using CNAME records, you will need to use 'A' records with the IP addresses of the customer sites directly instead of aliasing the names.

The first thing you need to do is determine who actually serves authoritative answers for your domain name. A WHOIS lookup will tell you which DNS servers are the ones where you should be making changes.

Once that is determined, make the changes with the provider listed and get rid of everything else to avoid any future confusion.

Regarding wildcards vs. hostnames, do whatever you're comfortable with. In general, most DNS implementations will look for a hostname that's been specifically defined (i.e. an A record that directs to a specific IP address) and will fall back to a wildcard if none is found. Personally, I prefer to define each of my records individually. This way I know what I have and where it goes without any questions. Wildcards can be great if you have 300 hostnames that all need to go to the same place and they change all the time. If you only have a handful of hostnames and they don't change often, I'd opt for setting them up individually.

If you have a dozen hostnames that all need to go to the same IP, you can define one of them as an A record, and make the rest CNAME aliases of the first one. This way, you only need to update that IP address once.