I'm working at a company which primarily provides SaaS products but also will host some of our customers corporate websites. My question relates to recommendations for managing DNS for client's domain names. My objectives:

1. Not restrict my ability to change the server's IP address such as might happen when I move my servers to a new host.
2. Not have to contact the customer to change their domain's DNS if I need to change the server's IP address. Often times, customers lose this information or have to track down the one person with any knowledge of the domain settings.
3. Map both .clientdomain.com and www.clientdomain.com to the proper IIS site.

However, I'm running into a couple of common problems:

1. Sometimes, the DNS console provided by the client's hosting company does not allow for CNAME records.
2. Sometimes, the DNS console provided by the client's hosting company will not let me create a CNAME entry for .spiffydomain.com because the given hosting company has created a SOA record for that entry or simply requires that .spiffydomain.com be an A record.

I believe one solution to #2 is to use a wildcard for a CNAME entry (i.e. *.spiffydomain.com). Is that correct?

How do other folks that are hosting many customer's site manage change of DNS entries on their servers?