Domain mapping DNS question

I’ve been using WPMU/multisite for a while now with domain mapping and it’s working ok. There is, however, something I’m starting to see an issue with and am wondering if there’s a fix for it.

Thus far, I’ve just been telling the domain owners to point their domain at my IP. And that’s working ok. However, soon I may be switching plans with my host and I’ve been informed I will not be able to take my current unique IP with me. That means if/when I make the move, I will have to contact all of the domain owners and tell them to make the change. That’s obviously going to be a pain.

I’m trying to figure out if I can simply provide them with either a domain or subdomain to use as a CNAME to point their domain at. What’s the best way to do this?

Thanks