mydomain.com - 11.22.333.4
* mydomain.com - 11.22.333.4
www mydomain.com - 11.22.333.4
mail mydomain.com - 11.22.333.4
This is what is set in my kloxo DNS template
base A 11.22.333.4
cp A 11.22.333.4
mail A 11.22.333.4
ns A 11.22.333.4
ns1 A 11.22.333.4
ns2 A 11.22.333.4
www A 11.22.333.4
ftp CN base
lists CN mail
webmail CN mail
www CN base
mydomain.com MX mail.mydomain.com
ns1.mydomain.com NS ns1.mydomain.com
ns2.mydomain.com NS ns2.mydomain.com
it is not correct. You have to set up an A record for the base domain and all subdomains each should have a separate record. You cannot use * and solve the problem. You also need to set up an A record for the mail server then you set up the MX record where you point the domain to the mail server with an integer value which would be the server priority. If you have only one server use 5 or 10
You set it where you are hosting your domains. Also if your customers wants you to keep their domains then you will have to do that for them otherwise you just let them take care of it. Usually the last is the case.
your bounced back mail should have some information in it. Either the email server is not accessible then you don't have an email server. If the MX record cannot be found then the DNS server is not populating.
What does the server which you shut down does? Why are you even shutting down a server? Servers are meant to stay up not turned off.